二分答案
二分答案的一般套路
最大值最小：
- 忽略极大值
- 保证全部能够分成<=x的m块
最小值最大：
- 忽略极小值
- 保证全部能够分成>=x的m块
整数二分
| 题目 | 题意 | 关键字/分析 | 题解 |
|---|---|---|---|
| 3745. 牛的学术圈 I | h指数:至少有h篇引用次数不少于h的论文,可以让m篇不同文章+1,求最小h的最大值 | 二分答案,贪心 | 题解 |
| P3853 路标设置 | 每个路标之间都有距离,可以安插路标减小距离,求最大距离最小 | 二分答案,贪心,推公式, | 题解 |
| 1659. 社交距离 I | 往牛棚中插入2头牛,使得每两头牛最小间隔最大 | 二分答案,推公式,贪心 | 题解 |
| P1314 聪明的质监员 | 题目太长…一道很奇特的二分答案题 | 二分答案,前缀和,三分 | 题解 |
| P3017 Brownie Slicing G | 有一个n*m的蛋糕,横着分成A块,然后每一块独立的竖着分成B块,求最小棋盘的最大值 | 二维前缀和,棋盘上的二分答案 | 题解 |
小数二分
| 题目 | 题意 | 关键字/分析 | 题解 |
|---|---|---|---|
| P1163 银行贷款 | 模板提,坑爹题 | 模板 | |
| 102. 最佳牛围栏 | 求每块地包含的牛的数量平均值最大值是多少,区域最少要包含F块地 | 二分答案,精度,双指针+前缀和妙用 | 题解 |
| p3743.kotori的设备 | k秒内消耗能量均为k*ai,初始有bi能量,每秒可充能p个单位,求最多一起使用多久 | 二分 | 题解 |
