二分答案有一个很显著的特征:一定存在一个临界值,单调性只是临界值的一种,而不是全部。
临界值,就是寻找第一个/最后一个满足要求的值,这又分别对应着两个完全不同的二分模板,这里做题时推荐使用“第一个满足要求的值”,即对应着 STL 中的 upper_bound ,手写板对应着 这篇文章 里讲的模板。
标志词
一些标志性词语:
- 最大值
- 最小值
- 最大化最小值
- 最小化最大值
- 第一个...
- 最后一个 ...
进阶技巧
一些进阶技巧:
- 对于在某区间内存在临界值或有单调性,但放在全局看就不满足的话,可以把全局分割成几个小区间,对每个小区间进行二分。如 [ CSP-J 2022 ] 解密 中把一个二次函数以顶点为分界,在左右端分别进行查找;[ NOIp 2001 提高组 ] 一元三次方程 因为根与根之间的差大于等于 \(1\) ,所以可以每隔 \(1\) 为一个分界点,对于每个区间 \(1\) 分别进行二分即可。
常见套路
一些常见套路:
- 二分+贪心的使用,先二分出当前答案,然后进行贪心看是否合法。例如 小鸟的设备、数列分段 II 、进击的奶牛 。
- 二分求中位数,原理是大于等于 \(mid\) 的数的个数和大=小于 \(mid\) 的数的个数的关系进行二分,例如 最大战力 (题解) 。
- 二分+判断答案可行性,“判断答案可行性” 里可以很多算法搭配使用。例如 汽车拉力比赛、营救。