浅谈二分—— by hyl天梦
二分
解决范围
二分法可以用来解决这一系列具有单调性质的题，例如求单调函数的零点
其实在小学奥数中就用到了二分法
例如手动开根号，再比如猜数游戏
二分的具体过程就是先取一个中间值，判定一下正确答案在哪边，然后接着再二分，直到找到答案为止
二分法的本质是把求解问题转化成判定问题
优势
二分相对于暴力枚举来讲，判定次数会显著变少
具体来说，如果暴力枚举期望是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的最值