二分搜索
二分搜索可以看成在单调区间上的枚举的优化
通常适用于 双指针问题，枚举优化问题
整数二分
| 题目 | 题意 | 关键字/分析 | 题解 |
|---|---|---|---|
| 1236.递增三元组 | 统计多少个三元组(i,j,k)满足 1<=i,j,k<=N, Ai<Bj<Ck | 二分,双指针,前缀和 | |
| 1221.四平方和 | 求一个数被表示成最小字典序的由4个数字平方和构成的方案 | 二分,以空间换时间 | 题解 |
| 智乃的密码 | 把字符定义成3种类型,求一个串中有多少个不同类型>=3的子串,子串长度[l,r] | 二分,推公式 | 题解 |
| 小沙的炉石 | 有n张攻击牌,m张法术回复牌,回复牌恢复一点蓝,刚开始攻击为1,每用一张牌永久加1,求有没有一种方法能够将对手恰好斩杀 | 二分,结论,区间合并 | 题解 |
小数二分模板
790.数的三次方根
二分答案
根据本菜鸡的经验,二分答案的check()一般有两种
一般是检验条件是否合理
- 计数性,枚举某个物品 出现/使用 的数量 <=限制
- 可行性,某个条件是否能够达到
整数二分
| 题目 | 题意 | 关键字/分析 | 题解 |
|---|---|---|---|
| 1227.分巧克力 | 有n块巧克力,每块巧克力都是H*W大小的长方形,求分出k块小巧克力的最大边长 | 二分答案模板 | |
| 730.机器人跳跃问题 | 每次跳跃能量都会变成2*e-h,求最小初始能量 | 二分答案模板 | 题解 |
| P2678 跳石头 | 有n个石头,组委会最多移走m个石头,求最短距离最大 | 二分答案,贪心 | 题解 |
| P1182 数列分段 Section II | 求把一个长度为n的数量,分成连续的m段,最大值最小是多少 | 题解 |
