【解雨臣的算法课】第二课：二分答案——找对位置，胜过盲目使劲
“在墓里，最忌讳的就是瞎摸。每一寸墙都摸一遍？等你摸到机关，氧气早没了。”
——解雨臣
一、上节课回顾
上一课我们讲了复杂度分析。为什么？
因为王胖子用 O(n!) 的算法去开青铜门，门没开，人先没了。
上节课的作业还有人记得吗？那道区间和等于 k 的题，不同数据范围要用不同算法：
- n \le 1000：O(n^2) 暴力枚举
- n \le 10^5：前缀和 + 哈希表 O(n)
这就是看到数据范围，选择合适算法。
今天我们来讲一个更骚的操作：既然直接找找不到，那我就猜，然后验证。
二、故事引入：解雨臣找机关
有一次下斗，我进了一间墓室。
墓室很大，四周全是壁画。根据经验，这间墓室一定有机关，打开了才能进下一层。
但是机关在哪？
胖子说：“摸！每块砖都摸一遍！”
我拦住了他。
因为这间墓室有 10^5 块砖。
一块砖摸一秒钟，摸完要 10^5 秒 ≈ 27.7 小时。等摸完，氧气早就没了。
我问黑瞎子：“你有什么办法？”
黑瞎子说：“机关的高度肯定在某个范围内。咱们猜一个高度，然后验证那个高度有没有机关。”
我说：“猜错了呢？”
黑瞎子说：“猜错了就调整。高了往下猜，低了往上猜。”
我说：“这不就是…”
黑瞎子说：“二分。”
三、什么是二分答案？
二分答案，就是对答案进行二分查找。
等等，答案还能二分？
普通二分 vs 二分答案
| 类型 | 普通二分 | 二分答案 |
|---|---|---|
| 二分对象 | 数组下标 | 答案的值 |
| 查找内容 | 某个数在不在 | 可行解的最值 |
| 前提 | 数组有序 | 答案具有单调性 |
| 经典问题 | 二分查找 | 最小值最大、最大值最小 |
核心思想：如果我直接求最优解很难，但是给我一个解，我能判断它行不行——那我就二分这个解。
四、二分答案的套路模板
// 解雨臣牌二分答案模板
bool ck(int x) {
// 验证 x 是否可行
// 返回 true 表示可行，false 表示不可行
}
int sol() {
int l = 最小值; // 答案可能的最小值
int r = 最大值; // 答案可能的最大值
int ans = l; // 记录答案
while (l <= r) {
int mid = (l + r) / 2;
if (ck(mid)) {
ans = mid; // mid 可行，记录答案
l = mid + 1; // 尝试更大的（求最大值时）
// 如果是求最小值，则 r = mid - 1
} else {
r = mid - 1; // mid 不可行，缩小范围
}
}
return ans;
}
关键：一定要想清楚——
- 我二分的是什么？
- 可行解的定义是什么？
- 单调性体现在哪？
五、经典例题：解雨臣切木头
题目背景
我从墓里带出来一批木头，准备切成等长的小段做机关。
有 n 根木头，长度分别为 a_1, a_2, ..., a_n。
我要把它们切成至少 k 段，每段长度相等（可以是小数？不，木头只能切整数长度）。
求每段最长能切多长。
题目重述
- 输入：n, k，数组 a
- 输出：最大长度 L，使得能切出至少 k 段长度为 L 的木头
思路分析
如果我会魔法，一眼看出 L 是多少，那就直接输出。
但我是解雨臣，不会魔法。
不过我会验证：
给我一个 L，我能算出最多能切多少段：
$$\text{段数} = \sum_{i=1}^n \lfloor \frac{a_i}{L} \rfloor$$
如果段数 \ge k，说明 L 可行；
如果段数 < k，说明 L 太大，切不出那么多段。
单调性：
- L 越小，能切的段数越多
- L 越大，能切的段数越少
- 我们要找的是满足段数 \ge k 的最大 L
代码实现
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, k;
int a[N];
bool ck(int x) {
if (x == 0) {
return true; // 长度为0肯定可以，但实际不会取0
}
long long cnt = 0;
for (int i = 1; i <= n; i++) {
cnt += a[i] / x;
if (cnt >= k) {
return true; // 提前退出
}
}
return cnt >= k;
}
int main() {
cin >> n >> k;
int mx = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
mx = max(mx, a[i]);
}
int l = 1, r = mx, ans = 0;
while (l <= r) {
int mid = (l + r) / 2;
if (ck(mid)) {
ans = mid;
l = mid + 1; // 找更大的
} else {
r = mid - 1;
}
}
cout << ans << endl;
return 0;
}
复杂度分析
- 二分次数：O(\log(\max a_i))
- 每次 ck：O(n)
- 总复杂度：O(n \log(\max a_i))
对于 n = 10^5，\max a_i = 10^9，大约 10^5 \times 30 = 3 \times 10^6 次运算，稳稳通过。
六、经典例题2：解雨臣跳石头
题目背景
我要过一条河，河里有 n 块石头，位置分别是 $p_1 < p_2 < … < p_n$（坐标）。
我可以最多搬走 m 块石头（让它们消失）。
起点是 0，终点是 L。
我要跳着石头过河，每次只能跳到石头上或者终点。
问：搬走 m 块石头后，最短跳跃距离的最大值是多少？
思路分析
又是最大值最小问题。
直接求：不知道搬哪 m 块。
用二分答案：
给我一个最短跳跃距离 d，我能判断：能否通过搬走不超过 m 块石头，使得所有相邻落脚点的距离都 \ge d？
验证方法（贪心）：
- 从起点开始跳
- 如果下一块石头距离 < d，就搬走它
- 如果距离 \ge d，就跳上去
- 最后统计搬走了多少块，如果 \le m 则可行
单调性：
- d 越小，越容易满足（要搬的石头少）
- d 越大，越难满足（要搬的石头多）
- 我们要找的是满足条件的最大的 d
代码实现
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int L, n, m;
int p[N];
bool ck(int d) {
int lst = 0; // 上一次跳到的位置
int cnt = 0; // 搬走的石头数
for (int i = 1; i <= n; i++) {
if (p[i] - lst < d) {
cnt++; // 这块石头得搬走
} else {
lst = p[i]; // 跳上去
}
}
// 最后还要检查从最后一块石头到终点
if (L - lst < d) {
return false; // 最后一段跳不过去
}
return cnt <= m;
}
int main() {
cin >> L >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> p[i];
}
int l = 1, r = L, ans = 0;
while (l <= r) {
int mid = (l + r) / 2;
if (ck(mid)) {
ans = mid;
l = mid + 1; // 找更大的
} else {
r = mid - 1;
}
}
cout << ans << endl;
return 0;
}
七、什么时候用二分答案？
解雨臣的经验总结：
适用条件：
- 答案在一个固定范围内（知道 l 和 $r$）
- 容易验证一个答案是否可行（ck 函数好写）
- 答案具有单调性（$x$ 可行则 <x 或 >x 也可行）
常见题型：
- 最大值最小（如：最大距离的最小值）
- 最小值最大（如：最小距离的最大值）
- 满足条件的最值
经典问题：
- 切木头/切绳子（最大值最小）
- 跳石头（最小值最大）
- 进击的奶牛（最小值最大）
- 月度开销（最大值最小）
- 实数二分（求平方根、解方程）
八、解雨臣踩过的坑
坑1：边界条件
while (l < r) 还是 while (l <= r)？
l = mid 还是 l = mid + 1？
解家箴言：拿不准就写 while (l <= r) 配合 ans 记录，保命第一。
坑2：死循环
while (l < r) {
int mid = (l + r) / 2;
if (ck(mid)) {
l = mid;
} else {
r = mid - 1;
}
}
// 当 l = 1, r = 2 时，mid = 1，如果 ck(1) 为真，l 还是 1，死循环！
解家箴言：小心边界，不行就加1：
int mid = (l + r + 1) / 2; // 向上取整，避免死循环
坑3：实数二分
while (r - l > eps) {
double mid = (l + r) / 2;
if (ck(mid)) {
l = mid;
} else {
r = mid;
}
}
解家箴言：eps 通常取 1e-7 或 1e-9，别太小，否则死循环。
坑4：ck 函数写错
这是最常见的。ck 写错了，二分出来的答案也是错的。
解家箴言：先暴力验证小数据，ck 对不对。
九、课后习题（解家的考验）
基础题
-
切绳子：有 n 条绳子，长度分别为 L_i。要切成 k 条长度相等的绳子，求最长能切多长？（实数）
-
进击的奶牛：有 n 个牛棚，位置 x_i。要把 c 头牛放进牛棚，要求相邻牛的最小距离最大，求这个最大距离。
进阶题
- 月度开销：FJ 要把 n 个月的开销 a_i 分成 m 个连续的月份组，使得各组开销之和的最大值最小，求这个最小值。
挑战题（来自青铜门的考验）
- 解雨臣的机关：一个机关有 n 个齿轮排成一排，每个齿轮有半径 r_i。我要让相邻齿轮都啮合（即相邻半径之和 $\ge k$）。我可以把某些齿轮替换成任意半径，但最多替换 m 个。求所有相邻齿轮啮合时，最小半径的最大值是多少？
提示：二分答案 + 贪心验证，类似跳石头但更复杂。
十、下集预告
“二分答案就像下斗——你先猜机关在哪，然后伸手去摸。摸到了，就继续往前；摸不到，换个方向再猜。”
——解雨臣
下一课，我们将进入提高组的第一个数据结构：前缀和与差分。
为什么？
因为很多二分答案的 ck 函数里，需要快速求区间和。
而前缀和，就是最快的区间求和法。
下课。
（本系列课程由解雨臣独家赞助，信友队论坛首发。转载需注明出处，否则下次下斗不带你。）
