摘要
本节主要关于二分与三分的问题，二分与三分时我们通常会区分整数和浮点而做不同的处理。
整数二分
最经典的一类，我们通常这样写
int L=... , R = ...; while(R>L) { ... if(...) L=mid+1; else R=mid; } cout<<L (-1) <<endl;
需要注意的是在这里最终答案是否-1取决于L=mid+1这一切换进行时，mid是否为合法解。如果是，那么-1. 如果不是，就输出L。
当然还存在一些别的写法，比如将判断条件改为R>=L，切换语句写作L=mid+1,r=mid-1，同时记录最后一次合法的Ans。弄清楚一种即可。
浮点数二分
浮点类二分非常容易，只需要注意控制精度误差即可。
浮点数三分
三分法通常用于找凸函数极值（虽然理论上对导函数二分也挺好），这时候需要用到两个mid值，即m1和m2，分别对应区间[l,r]的两个三等分点，计算出两个三等分点，然后根据需要将左端点缩到左三等分点，或者右端点缩到右三等分点，这样来进行转移即可。在浮点数情况下实现是很容易的。
整数三分
有时候我们需要对整数三分，就需要注意一下取整误差的问题，提供参考写法如下。
int l=..., r=...; while(r>l){ int m1=(2*l+r)/3, m2=(2*r+l+2)/3; if(...) r=m2-1; else l=m1+1; } cout<<l<<endl;
二分答案+验证
如果问题的答案与决定性参变量的函数关系是非严格单调的，我们就可以用二分来将它转化为若干判定性问题，这在处理很多问题时是非常有效的。
二分套二分/三分套三分
当决定性参变量有多个，并且函数对每个参变量的偏导数都是恒非正或恒非负的时候，我们既可以用二分套二分来解决问题。即对f(x,y)，我们先二分一个x，将它转化为f(x,y)=g(y)，然后求出g(y)的答案，就得到了f(x,y)在这个x上的答案。
LOJ10011. 「一本通 1.2 例 1」愤怒的牛
#include <bits/stdc++.h> using namespace std; int n,m,a[1000005]; int main() { cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]; sort(a+1,a+n+1); int l=0,r=1e+9; while(r>l) { int mid = (l+r)/2; int las = -1e+9, cnt = 0; for(int i=1;i<=n;i++) if(a[i]-las >= mid) ++cnt, las = a[i]; if(cnt>=m) l=mid+1; else r=mid; } cout<<l-1<<endl; }
LOJ10012. 「一本通 1.2 例 2」Best Cow Fences
这里涉及到二分答案的一个常用技巧，即对分数形式，比如这里的ans = (sum(...))/(sum(1))，我们二分一个ans，那么不等式ans > (sum(...))/(sum(1))就可以转化为sum(a[i]-ans)>0，通过后缀最大值处理一下就可以了。
浮点数问题一定要注意补偿舍入误差。
#include <bits/stdc++.h> using namespace std; int n,l,a[1000005]; double s[1000005]; int main() { cin>>n>>l; for(int i=1;i<=n;i++) cin>>a[i]; double L=0, R = 1e+9; while(R-L > 1e-6) { double mid = (L+R) / 2.0; for(int i=1;i<=n;i++) s[i] = s[i-1] + a[i] - mid; int flag = 0; s[n+1] = -1e+19; for(int i=n-l;i>=0;--i) s[i+l] = max(s[i+l], s[i+l+1]), flag |= (s[i+l]-s[i]>-1e-6); if(flag) L=mid; else R=mid; } cout<<(int)(L*1000.0+0.005)<<endl; }
#10013. 「一本通 1.2 例 3」曲线
#include <bits/stdc++.h> using namespace std; int T,n; double a[10005],b[10005],c[10005],t1,t2,t3; double f(double x) { double ret = -1e+18; for(int i=1;i<=n;i++) ret = max(ret, a[i]*x*x+b[i]*x+c[i]); return ret; } int main() { ios::sync_with_stdio(false); cin>>T; while(T--) { cin>>n; double ans = -1e+18; for(int i=1;i<=n;i++) cin>>a[i]>>b[i]>>c[i]; double l=0,r=1000; while(r-l > 1e-11) { double m1 = l + (r-l)/3.0, m2 = r - (r-l)/3.0; if(f(m1)>f(m2)) l=m1; else r=m2; } cout<<setiosflags(ios::fixed)<<setprecision(4)<<f(l)<<endl; } }
#10014. 「一本通 1.2 练习 1」数列分段 II
#include <bits/stdc++.h> using namespace std; int n,m,a[1000005]; int main() { cin>>n>>m; int mx=0; for(int i=1;i<=n;i++) cin>>a[i], mx=max(mx,a[i]); int l=mx,r=1e+9; while(r-l>0) { int mid = (l+r)/2; int sum = 0, cnt = 1; for(int i=1;i<=n;i++) { if(sum+a[i]>mid) ++cnt,sum=0; sum+=a[i]; } if(cnt<=m) r=mid; else l=mid+1; } cout<<l<<endl; }
#10015. 「一本通 1.2 练习 2」扩散
二分答案后考虑如何检验，暴力枚举点对看是否直接相连，并查集维护连通性即可。
#include <bits/stdc++.h> using namespace std; int n,x[100005],y[100005],f[105]; int find(int x) { return (f[x]==x)?x:(f[x]=find(f[x])); } int dis(int x1,int y1,int x2,int y2) { return abs(x1-x2) + abs(y1-y2); } int main() { cin>>n; for(int i=1;i<=n;i++) cin>>x[i]>>y[i]; int l=0,r=1e+9; while(r-l) { int mid = (l+r)/2, cnt = n; for(int i=1;i<=n;i++) f[i]=i; for(int i=1;i<=n;i++) for(int j=1;j<i;j++) if(dis(x[i],y[i],x[j],y[j])<=2*mid) if(find(i)!=find(j)) f[find(i)]=find(j), --cnt; if(cnt==1) r=mid; else l=mid+1; } cout<<l<<endl; }
#10016. 「一本通 1.2 练习 3」灯泡
几何推公式
#include <bits/stdc++.h> using namespace std; int T; double H,h,D; double f(double x) { double ret = h/(H-h)*x; if(ret+x > D) ret = D - x + (ret+x - D) * (H-h) / x; return ret; } int main() { cin>>T; while(T--) { cin>>H>>h>>D; double L=0,R=D; while(R-L > 1e-8) { double m1 = L + (R-L)/3, m2 = R - (R-L)/3; if(f(m1)>f(m2)) R=m2; else L=m1; } cout<<setiosflags(ios::fixed)<<setprecision(3)<<f(L)<<endl; } }
#10017. 「一本通 1.2 练习 4」传送带
三分套三分，设两个比例k,u。
#include <bits/stdc++.h> using namespace std; double ax,ay,bx,by,cx,cy,dx,dy,p,q,r; double f(double x1,double y1,double x2,double y2) { return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); } double calc(double k,double u) { double x1=k*ax+(1-k)*bx, y1=k*ay+(1-k)*by; double x2=u*cx+(1-u)*dx, y2=u*cy+(1-u)*dy; return f(ax,ay,x1,y1)/p+f(x1,y1,x2,y2)/r+f(x2,y2,dx,dy)/q; } double inner(double m) { double L=0,R=1; while(R-L > 1e-8) { double m1=L+(R-L)/3, m2=R-(R-L)/3; if(calc(m,m1)<calc(m,m2)) R=m2; else L=m1; } return calc(m,L); } int main() { cin>>ax>>ay>>bx>>by>>cx>>cy>>dx>>dy>>p>>q>>r; double L=0,R=1; while(R-L > 1e-8) { double m1=L+(R-L)/3, m2=R-(R-L)/3; if(inner(m1)<inner(m2)) R=m2; else L=m1; } cout<<setiosflags(ios::fixed)<<setprecision(2)<<inner(L)<<endl; }
#include <bits/stdc++.h>using namespace std;
double ax,ay,bx,by,cx,cy,dx,dy,p,q,r;
double f(double x1,double y1,double x2,double y2) { return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}
double calc(double k,double u) { double x1=k*ax+(1-k)*bx, y1=k*ay+(1-k)*by; double x2=u*cx+(1-u)*dx, y2=u*cy+(1-u)*dy; return f(ax,ay,x1,y1)/p+f(x1,y1,x2,y2)/r+f(x2,y2,dx,dy)/q;}
double inner(double m) { double L=0,R=1; while(R-L > 1e-8) { double m1=L+(R-L)/3, m2=R-(R-L)/3; if(calc(m,m1)<calc(m,m2)) R=m2; else L=m1; } return calc(m,L);}
int main() { cin>>ax>>ay>>bx>>by>>cx>>cy>>dx>>dy>>p>>q>>r; double L=0,R=1; while(R-L > 1e-8) { double m1=L+(R-L)/3, m2=R-(R-L)/3; if(inner(m1)<inner(m2)) R=m2; else L=m1; } cout<<setiosflags(ios::fixed)<<setprecision(2)<<inner(L)<<endl;}