二分答案估计是我应该早就学会，但拖到现在才去好好看的套路吧！
二分答案是指在答案具有单调性的前提下，利用二分的思想枚举答案，将求解问题转化为验证结果。首先需要估计答案的上下界，然后不断取区间中点进行验证（这就要求答案的验证应当简单可行），并通过验证结果不断更新答案区间，最终得到答案。不难看出，朴素的枚举验证时间复杂度是O(n)的，而二分可以做到O(logn)。更令人欣喜的是，二分答案的问题往往有固定的问法，比如：令最大值最小（最小值最大），求满足条件的最大（小）值等。
一道模板题练个手：https://www.luogu.org/problemnew/show/P2678
这几乎是最简单的二分答案模板题，在明白二分答案后，是可以做到一遍AC的。题目的问法也十分模板（求最短跳跃距离的最大值），答案是单调的，拿走的石头越多，最短跳跃距离越大。我们可以估计最大的最短跳跃距离(1<=ans<=L)。然后取区间中点，进行验证。若发现某次跳跃比这个最短跳跃距离还小，那就把这块石头拿走。总共拿走的石头数不超过M，就说明区间中点符合要求，就将区间更新为右半区间（因为要求最大的最短跳跃距离）；反之，就将区间设为左半区间。
1 #include<cstdio> 2 #include<cctype> 3 inline int get_num() { //读入优化 4 int num; 5 char c; 6 while((c=getchar())==‘\n‘||c==‘ ‘||c==‘\r‘); 7 num=c-‘0‘; 8 while(isdigit(c=getchar())) num=num*10+c-‘0‘; 9 return num; 10 } 11 const int maxn=5e4+5; 12 int L,n,m,d[maxn]; 13 bool check(int x) { //检验答案是否符合要求 14 int last=0,cnt=0; 15 for(int i=1;i<=n;++i) { 16 if(d[i]-last<x) ++cnt; //拿走石头 17 else last=d[i]; //跳出不影响答案的一步 18 } 19 return cnt<=m?true:false; 20 } 21 int main() { 22 L=get_num();n=get_num();m=get_num(); 23 for(int i=1;i<=n;++i) d[i]=get_num(); 24 d[++n]=L; //注意，最终要跳到终点 25 int l=0,r=L+1; 26 while(r-l>1) { 27 int mid=l+(r-l)/2; 28 if(check(mid)) l=mid; //调整区间 29 else r=mid; 30 } 31 printf("%d",l); 32 return 0; 33 }
原文：https://www.cnblogs.com/Mr94Kevin/p/9538431.html
