答案的单调性大多数情况下可以转化为一个函数，其单调性证明多种多样，如下：
移动石头的个数越多，答案越大（NOIP2015跳石头）。
前i天的条件一定比前 i + 1 天条件更容易（NOIP2012借教室）。
满足更少分配要求比满足更多的要求更容易（NOIP2010关押罪犯）。
满足更大最大值比满足更小最大值的要求更容易（NOIP2015运输计划）。
时间越长，越容易满足条件（NOIP2012疫情控制）。
可以解决的问题
求最大的最小值（NOIP2015跳石头）。
求最小的最大值（NOIP2010关押罪犯）。
求满足条件下的最小（大）值。
求最靠近一个值的值。
求最小的能满足条件的代价。
代码
为了保证解在二分搜索的区间里，故不同的问题有着不同（但相似）的写法，读者可以画一个区间模拟一下~
求最小值
int binary()
{
int l = 0, r = ll, mid;
while(l < r)
{
mid = (l + r) >> 1;
if(check(mid)) r = mid; //大多数题只要改改check()即可
else l = mid + 1;
}
return l;
}
1
2
3
4
5
6
7
8
9
10
11
求最大值
int binary()
{
int l = 0, r = ll, mid;
while(l < r)
{
mid = (l + r + 1) >> 1;
if(check(mid)) r = mid - 1;
else l = mid;
}
return l;
}
1
2
3
4
5
6
7
8
9
10
11
面对整数时的万能二分（近似万能）
int binary(int n)
{
int l = 1, r = maxn, ans = 0;
while(l <= r)
{
int mid = (l + r) >> 1;
if(c[mid] > a[n]) ans = mid, l = mid + 1; //判断条件与ans记录位置因题而异
else r = mid - 1;
}
return ans;
}
---------------------
作者：Mashiro_ylb
来源：CSDN
原文：https://blog.csdn.net/mashiro_ylb/article/details/78469151
版权声明：本文为博主原创文章，转载请附上博文链接！