二分
解决范围
二分法可以用来解决这一系列具有单调性质的题, 例如求单调函数的零点
其实在小学奥数中就用到了二分法
例如手动开根号, 再比如猜数游戏
二分的具体过程就是先取一个中间值, 判定一下正确答案在哪边, 然后接着再二分, 直到找到答案为止
二分法的本质是把求解问题转化成判定问题
优势
二分相对于暴力枚举来讲, 判定次数会显著变少
具体来说, 如果暴力枚举期望是 O(N)次
那么二分只需要 O(logN)次就可以得出答案
模板
- // 整数版
- while(l<r)
- {
- mid=(l+r)/2;
- if(check(mid)) r=mid;
- else l=mid+1;
- }
- while(l<r)
- {
- mid=(l+r+1)/2;// 注意 + 1
- if(check(mid)) l=mid;
- else r=mid-1;
- }
- // 小数版
- while(r-l>eps)
- {
- mid=(l+r)/2;
- if(check(mid)>0) l=mid;
- else r=mid-eps;
- }
- // 其中 eps=1e-6 或 1e-8; 依照题而定
例题
派
题目 1
我的生日要到了! 根据习俗, 我需要将一些派分给大家. 我有 N 个不同口味, 不同大小的派. 有 F 个朋友会来参加我的派对, 每个人会拿到一块派(必须一个派的一块, 不能由几个派的小块拼成; 可以是一整个派).
我的朋友们都特别小气, 如果有人拿到更大的一块, 就会开始抱怨. 因此所有人拿到的派是同样大小的(但不需要是同样形状的), 虽然这样有些派会被浪费, 但总比搞砸整个派对好. 当然, 我也要给自己留一块, 而这一块也要和其他人的同样大小.
请问我们每个人拿到的派最大是多少? 每个派都是一个高为 1, 半径不等的圆柱体.
代码 1
- #include<iostream>
- #include<cstdio>
- #include<algorithm>
- #include<cstring>
- #include<sstream>
- #include<queue>
- #include<vector>
- #define N 100010
- #define ll long long
- #define dd double
- using namespace std;
- int n,f;
- dd a[N];
- const dd pie=3.1415926535;
- bool check(dd mid)
- {
- ll sum=0;
- for(int i=1;i<=n;i++)
- {
- sum+=a[i]/mid;
- }
- if(sum>=f) return 1;
- else return 0;
- }
- int main()
- {
- cin>>n>>f;
- dd l=0,r=0;
- for(int i=1;i<=n;i++)
- {
- dd x;
- cin>>x;
- a[i]=x*x*pie*1;
- r=max(a[i],r);
- }
- dd eps=0.001;
- while(r-l>eps)
- {
- dd mid=(l+r)/2.0;
- if(check(mid)) l=mid;
- else r=mid-eps;
- }
- printf("%0.3lf",l);
- return 0;
- }
题目 2
把一个包含 n 个正整数的序列划分为 m 个连续的子序列 (每个正整数恰好属于一个序列). 设第 i 个序列的各数之和为 S(i), 你的任务是让所有 S(i) 的最大值尽量小.
例如序列 1 2 3 2 5 4 划分成 3 个序列的最优方案为 1 2 3|2 5 |4, 其中 S(1),S(2),S(3)分别为 6,7,4, 最大值为 7; 如果划分成 1 2|3 2|5 4, 则最大值为 9, 不如刚才的好.
n<=10^6, 所有数之和不超过 10^9.
代码 2
- #include<iostream>
- #include<cstdio>
- #include<algorithm>
- #include<cstring>
- #include<sstream>
- #include<queue>
- #include<vector>
- #define N 100010
- #define ll long long
- using namespace std;
- ll n,k,a[N];
- bool check(ll mid)
- {
- int sum=0,j=1;
- for(int i=1;i<=n;i++)
- {
- sum+=a[i];
- if(a[i]>mid) return 0;
- if(sum>mid)
- {
- j++;
- sum=a[i];
- }
- }
- if(j>k) return 0;
- else return 1;
- }
- int main()
- {
- scanf("%d%d",&n,&k);
- ll l,r=0;
- l=-100;
- for(int i=1;i<=n;i++)
- {
- scanf("%d",&a[i]);
- l=max(l,a[i]);
- r+=a[i];
- }
- while(l<r)
- {
- ll mid=l+r>>1;
- if(check(mid)) r=mid;
- else l=mid+1;
- }
- cout<<l<<endl;
- return 0;
- }
题目 3
公园里有 n 个水塘, 需要把这 n 个水塘中的水排干, 水塘中的水在自然条件下 1 个单位的时间可以蒸发 A 升水. 现在买了 1 台抽水机, 使用抽水机可以让你用 1 个单位的时间使每个水塘除开自然蒸发的 A 升水外, 还可抽 B 升水, 但在 1 个单位的时间内只能对 1 个水塘使用.
要你求出排干所有水塘的最少时间(水塘中的水为 0 时为排干).
代码 3
- #include<iostream>
- #include<cstdio>
- #include<algorithm>
- #include<cstring>
- #include<sstream>
- #include<queue>
- #include<vector>
- #define N 100010
- #define ll long long
- using namespace std;
- ll n,a[N],A,B;
- bool check(ll mid)
- {
- int sum=0;
- int jian=mid*A;
- for(int i=1;i<=n;i++)
- {
- int ai=a[i]-jian;
- if(ai>0)
- {
- sum+=ai/B;
- if(ai%B!=0) sum++;
- }
- }
- if(sum>mid) return 0;
- else return 1;
- }
- int main()
- {
- cin>>n>>A>>B;
- ll l=0,r=0;
- for(int i=1;i<=n;i++)
- {
- cin>>a[i];
- r+=a[i];
- }
- while(l<r)
- {
- ll mid=l+r>>1;
- if(check(mid)) r=mid;
- else l=mid+1;
- }
- cout<<l<<endl;
- return 0;
- }
- /*
- 5 3 4
- 19 12 15 23 7
- 答案: 5
- */
题目 4
给出两个长度为 n 的正整数有序数组 A 和 B, 在 A 和 B 中各任取一个, 可以得到 n*n 个积. 求第 n 小的元素.
n<=100000
思路 4
判定有多少乘积小于这个答案就可以继续二分
但是怎么判定呢?
由于两个数组都是有序的, 所以 A 数组中可行的乘积对应 B 数组一定是从头开始的一段序列, 并且范围逐渐变小
这样我们 O(N)扫一遍, 用一个指针维护一下 B 数组合法位置就可以了
代码 4
- #include<iostream>
- #include<cstdio>
- #include<algorithm>
- #include<cstring>
- #include<sstream>
- #include<queue>
- #include<vector>
- #define N 100010
- #define ll long long
- #define dd double
- using namespace std;
- ll n/*,m*/,a[N],b[N];
- bool check(ll mid)
- {
- int sum=0,j=1,i=n;
- while(i>=1&&j<=n)
- {
- if(a[i]*b[j]<mid)
- {
- sum+=i;
- j++;
- }
- else i--;
- }
- //cout<<sum+1<<endl;
- sum++;
- if(sum<=n) return 1;
- else return 0;
- }
- int main()
- {
- cin>>n;
- ll l=0,r=0;
- ll max1;
- for(int i=1;i<=n;i++) cin>>a[i],r=max(r,a[i]);
- for(int i=1;i<=n;i++) cin>>b[i],max1=max(max1,b[i]);
- r=max1*r;
- //cin>>m;check(m);
- while(l<r)
- {
- ll mid=l+r+1>>1;
- if(check(mid)) l=mid;
- else r=mid-1;
- }
- cout<<l<<endl;
- return 0;
- }
- /*
- #include<iostream>
- #include<cstdio>
- #include<algorithm>
- #include<cstring>
- #include<sstream>
- #include<queue>
- #include<vector>
- #define N 100010
- #define ll long long
- #define dd double
- using namespace std;
- ll n,a[N],b[N],c[N],tail;
- int main()
- {
- cin>>n;
- for(int i=1;i<=n;i++) cin>>a[i];
- for(int i=1;i<=n;i++) cin>>b[i];
- for(int i=1;i<=n;i++)
- for(int j=1;j<=n;j++)
- c[++tail]=a[i]*b[j];
- sort(c+1,c+tail+1);
- cout<<c[n];
- }
- */
- /*
- 5
- 12 23 112 231 345
- 23 123 423 2390 8492
- 答案: 2829
- 5
- 1 2 3 4 5
- 2 3 4 5 6
- 答案: 5
- */
题目 5
一年一度的 "跳石头" 比赛又要开始了!
这项比赛将在一条笔直的河道中进行, 河道中分布着一些巨大岩石. 组委会已经选择好了两块岩石作为比赛起点和终点. 在起点和终点之间, 有 N 块岩石(不含起点和终点的岩石). 在比赛过程中, 选手们将从起点出发, 每一步跳向相邻的岩石, 直至到达终点.
为了提高比赛难度, 组委会计划移走一些岩石, 使得选手们在比赛过程中的最短跳跃距离尽可能长. 由于预算限制, 组委会至多从起点和终点之间移走 M 块岩石(不能移走起点和终点的岩石).
求最短跳跃距离的最大值
N,M<=50000
代码 5
- #include<iostream>
- #include<cstdio>
- #include<algorithm>
- #include<cstring>
- #include<sstream>
- #include<queue>
- #include<map>
- #include<vector>
- #include<set>
- #include<deque>
- #define dd double
- #define ll long long
- #define N 10000100
- using namespace std;
- ll n,m,a[N];
- ll l;
- bool check(ll mid)
- {
- int now=0;
- int sum=0;
- for(int i=1;i<=n+1;i++)
- {
- if(a[i]-a[now]<mid) sum++;
- else now=i;
- }
- //cout<<mid<<" "<<sum<<endl;
- if(sum<=m) return 1;
- else return 0;
- }
- int main()
- {
- cin>>l>>n>>m;
- for(int i=1;i<=n;i++)
- {
- cin>>a[i];
- }
- a[n+1]=l;
- ll r=l;
- l=0;
- while(l<r)
- {
- ll mid=l+r+1>>1;
- if(check(mid)) l=mid;
- else r=mid-1;
- }
- cout<<l<<endl;
- return 0;
- }
三分
与二分法类似, 三分法可以用来解决具有单峰性质的题
三分的具体过程就是先取两个中间值, 分别位于 1/3 和 2/3 处, 根据单峰性判定一下正确答案在前 2/3 还是后 2/3, 然后接着再三分, 直到找到答案或答案的近似值为止
二分法每次把答案范围缩小一半, 三分法每次把答案范围变为原来的 2/3, 他们的时间复杂度都是 O(log(n))的
题目 1
在一个 2 维平面上有两条传送带, 每一条传送带可以看成是一条线段. 两条传送带分别为线段 AB 和线段 CD. 小 y 在 AB 上的移动速度为 P, 在 CD 上的移动速度为 Q, 在平面上的移动速度 R. 现在小 y 想从 A 点走到 D 点, 他想知道最少需要走多长时间?
思路 1
小 y 走的路径一定是三条线段组成的折线
如果把离开 AB 线段的点设为 x, 到达 CD 的点设为 y, 总时间设为 z, 那么 z 是关于 x,y 的二元函数
可以证明这个函数形如一个山丘, 也就是说可以先三分 x 再三分 y 求出 z 的最值
代码 1
详见 https://www.cnblogs.com/TianMeng-hyl/p/12309214.html
来源: https://www.cnblogs.com/TianMeng-hyl/p/12311214.html