| 基础算法·二分答案 | 您所在的位置：网站首页 › 什么是二分算法 › 基础算法·二分答案 |
基础算法·二分答案
|
题目链接
摸鱼助教Mogg Ⅱ 洛谷原题（除了多组数据都是相同的）链接：P1182 数列分段Section II 解题思路二分答案。 什么？什么是二分答案？我没听过 不要紧，希望这篇文章能帮助不会二分答案的你更好地理解二分的思想。 （神犇求放过） 不扯了，谈正题。大家都做过一个单调递增函数找零点的题吧，比如这个 还记得怎么做么？什么，没记得做过这个题？那请您先去做一遍。 先回到最初的起点。在我们初入程设的时候，循环语句就成为陪伴我们的梦魇朋友。就拿这个题举例子吧，我可以写一个这样的程序来做这道题： #include #include #define pi acos(-1)//π的常用定义方法，建议记住 double f(double x,double y){ return (sin(sqrt(x))+exp(-pow(x,1.0/3)))/log(pi*x)-y; //易错点！！！！！写成1/3就错了！！！千万千万要注意！ } int main(){ double i,y; scanf("%lf",&y); for(i=0.33;i0)left=mid;//如果大于零，那么删掉左区间 else right=mid;//否则删掉右区间 } printf("%.5f",left); return 0; }
这就很快乐了。注意到，这种精度能达到\(1e-10\)的程序只需要\(9ms\)，相比之下暴力循环求解精度\(1e-6\)都要\(TLE\)。 其实，可以证明，这种算法的复杂度是\(O(log n)\)的。 回顾一下做这个题的思路。因为函数具有单调性，所以可以通过不断二分达到不断缩小答案区间的目的。请仔细理解这句话。 现在再回去看这道题。从头开始，倒霉的学弟学妹开始每个人搬一堆书，这道题的意思就是问所有人中，搬书重量最大的那个人搬书重量的最小值。 什么意思呢？ 简单来说，就是把每个人要搬的所有书（假设书的高度与重量成正比）摞起来，再拿一个标尺，问这个标尺至少要多高才能把所有人的书都盖住。 那么我们现在看的这个标尺，是不是和刚刚的那个函数有点相像啊？ 我当然可以通过枚举标尺的高度得到答案，但是会慢很多。 于是，我们可以二分地寻找这个标尺的高度，这类似寻找刚刚函数的零点。 找到一个答案下限，找到一个答案上限，在这个区间内二分查找合理答案。 请思考：这个答案下限和答案上限分别是多少？ 想好了再回来。不给出答案。直接贴代码。 #include int a[100010]; int main(){ int n,m,i; while(~scanf("%d%d",&n,&m)){ //~是取反，相当于scanf()!=EOF //注意这里没有先初始化a[i]数组，因为没必要 //但是一定要注意有必要的时候千万别忘了初始化定义在外面的变量 int left=0,right=0; for(i=0;ileft)left=a[i]; right+=a[i]; } while(left |
【本文地址】
公司简介
联系我们