手机网站自助建,阿里云买啦域名怎么建设网站,用表格做网站教程,动态小网站之前学习的二分#xff0c;现在感觉突然理解许多#xff0c;补一下总结 首先#xff0c;二分能够解决什么样的问题呢#xff0c;个人认为#xff0c;二分能够快速解决已经知道答案范围#xff08;线性#xff09;但是不知道确切答案的问题#xff0c;例如在一个有序序列…之前学习的二分现在感觉突然理解许多补一下总结 首先二分能够解决什么样的问题呢个人认为二分能够快速解决已经知道答案范围线性但是不知道确切答案的问题例如在一个有序序列中查找某一元素出现的最早最晚位置求某单调或在给定区间上单调函数的零点最大化最小值或者最小化最大值等等 二分的模板大体如下
int lx;//x表示元素可能出现的最小最左边的情况
int ry;//y表示元素可能出现的最大最右边的情况
int ans,mid;
while(il)
{mid(lr)/2; //二分if(check(mid))//判断中点的情况{lmid1;ansmid; //或者ansmax(ans,mid)等ans用于保存答案如果需要所有可行答案中的最大值或者最小值加上max或者min即可}else{rmid-1;}
}总体来讲二分的思想还是比较简单的但是问题的难点经常不是考虑不到二分而是考虑到二分却不知道如何判断要查找的元素在mid的情况下能否可行即如何编写check(mid)函数。这个函数的编写往往要仔细考虑要查找元素的特征以及脑洞。 比如经常出现的最大化最小值和最小化最大值等那些放牛的等问题判断起来还是比较容易的就从开始一个一个按照条件放如果能行就能行。但是更多的问题还是比较灵活的比如POJ - 3104
题意大概是一个人冬天洗衣服想要让衣服尽快的干问最少需要多少时间。 这个我们很容易确定所花最长时间是水分最多的衣服所含有的水分不用那个烘干器自然风干最短时间为0但是给定一个时间我们怎么判断这个时间内可不可以将衣服晾干呢 这就需要我们进行一个转换我们不妨这样想这些衣服先晾了mid分钟然后再将还没有干的全部用烘干器烘干烘干器只能烘mid次每次烘干k-1的水分。 乍看好像有些无厘头其实仔细一想很简单我们只不过把原来一起做的事情拆开来分析而已表示不好想到。 这样的话我们遍历每件衣服如果它没有自己晾干就得用烘干器如果在mid次以内全部烘干了就可以如果没有就不行。 需要注意一点的是如果原本烘干器是个假的烘干器每分钟烘干的速度和晾衣服的速度一样那么只处理晾后的就不要用烘干器再处理了烘干器每次处理0不注意这点的话可能会re我re了好多次才注意到。
附AC代码
#includecstdio
#includecstring
#includealgorithm
using namespace std;int n,k;
int a[100100];bool cmp(int a,int b)
{return ab;
}
bool check(int time)
{int tmptime;int t;for(int i0;in;i){ta[i]-time;if(t0){if(k0)return false;tmp-t/k;if(t%k!0)tmp--;}if(tmp0)return false;}return true;
}
int main()
{int tmp;memset(a,0,sizeof(a));scanf(%d,n);for(int i0;in;i){scanf(%d,a[i]);}scanf(%d,k);k--;sort(a,an,cmp);int l0,ra[0];int ans0,mid;while(lr){mid(lr)/2;if(check(mid)){rmid-1;ansmid;}else{lmid1;}}printf(%d,ans);return 0;
}除此之外二分法快速幂也经常使用必须熟记虽然我觉得是一个递归 快速幂板子非递归写法
long long qucik_pow(long long a,long long n,long long m)//求a^n%m
{long long ans1;while(n){if(n1) ans(ans*a)%m;aa*a%m;n1;}return ans%m;
}还有递归写法有助于理解快速幂但是不常用
long long quick_pow(long long a,long long n,long long m)
{if(n1) return a;if(n%20){long long tquick_pow(a,n/2,m);return t*t%m;}else{long long tquick_pow(a,b/2,m);tt*t%m;tt*a%m;return t;}
}三分的话每太用过只是见过用来求凸凹函数的极值点 思想就是先将区间二分在将其中一个区间二分然后比较两个点的大小哪个距离极值点远就将哪一边更新应该是可以根据凹凸函数的性质进行证明的我比较懒就不证明了有时间再证吧附一下板子
while(leftepsright)
{midl(leftright)/2;midr(midlright)/2;if(f(midl)f(midr)){rightmidr;}else{leftmidl;}
}
