二分答案的套路非常反直觉，但一旦学会，你会在无数题里认出它：
题目问「最大值最小是多少」「最小值最大是多少」「最多能选几个」—— 十有八九是二分答案。
它的思路是：不直接求答案，而是猜一个答案，然后写个函数验证这个猜测行不行。
听起来像作弊，但它是完全严谨的。而且「验证」通常比「求解」简单一百倍 —— 这一章的验证函数只有 8 行，而直接求解要写动态规划。
第 8 章那个二分模板，这一章原封不动地用。变的只有 check。
1 一句话问题
给 n 个正整数排成一列，要把它切成不超过 m 段连续的子段。
每段有一个和，m 段里有一个最大的和。
问：怎么切，才能让「最大的那段和」尽量小？
输入 6 3
7 2 5 10 8 3
输出 14
切法：[7 2 5] [10] [8 3]
三段的和是 14、10、11，最大值 14。
再也找不到更小的了。「把 n 本书分给 m 个抄书员，每人抄连续的一段，问最累的那个人最少要抄多少页」—— 这就是洛谷 P1281。同一道题换了个皮。
「最大值最小化」的本质永远是：有一批任务要分配，想让最重的那个负担最轻。
2 先用纸笔手算一遍
7 2 5 10 8 3 切成 3 段，穷举几种切法：
[7] [2 5 10] [8 3] → 7, 17, 11 最大 17
[7 2] [5 10] [8 3] → 9, 15, 11 最大 15
[7 2 5] [10] [8 3] → 14, 10, 11 最大 14 ← 目前最好
[7 2 5] [10 8] [3] → 14, 18, 3 最大 18
[7 2 5 10] [8] [3] → 24, 8, 3 最大 24手算完你会有个感觉：「怎么切」这件事很难直接想清楚。 切法太多了（n 个位置里挑 m-1 个切点），而且好坏没有明显规律。
不要问「怎么切最好」，改成问：
「每段和都不超过 14」这个要求，能做到吗？
这个问题好回答得多：从左往右能装就装，装不下就另起一段，数一数用了几段。
上限 14： 7+2+5=14 装满了 | 10 | 8+3=11 用了 3 段 ≤ 3 → 能做到 ✓
上限 13： 7+2=9 | 5+... 装不下 10 | 10 | 8+3 用了 4 段 > 3 → 做不到 ✗于是「求最优解」变成了「验证一个猜测」。而答案， 就是所有能做到的上限里最小的那个。
3 验证函数：8 行贪心
// 每段和都不超过 limit，能不能只用 m 段装完？
bool ok(long long limit) {
int seg = 1; long long cur = 0;
for (int i = 1; i <= n; i++) {
if (a[i] > limit) return false; // 单个数就超了，怎么切都不行
if (cur + a[i] <= limit) cur += a[i]; // 塞进当前这段
else { seg++; cur = a[i]; } // 装不下，另起一段
}
return seg <= m;
}「能装就装」不会吃亏：当前这段多装一个数，剩下要装的东西就少一个， 后面只可能更轻松，绝不可能因此多用一段。
反过来，如果故意少装一个留到下一段，剩下的东西反而变多了，段数只会更多。
这个「多装绝不吃亏」的论证，就是贪心的正确性证明。 阶段 4（第 19、20 章）会专门讲怎么做这种论证 —— 现在先记住： 贪心不是「感觉对就行」，是要能说出为什么。
4 暴力：从小到大挨个试
有了 ok()，最笨的办法就是从最小的可能答案开始，一个一个往上试：
点「运行 ▶」看结果
答案不可能小于「最大的那个数」（它总得待在某段里），
也不可能大于「所有数之和」（那是只分一段）。所以从 max 试到 sum。
**这份代码是完全正确的。**它慢，但慢得很诚实 —— 待会儿它就是对拍的标准答案之一。
5 实测：它有多慢
本机实测（数值 1~100000，段数 n/10）：
| n | 逐个试 | 二分着试 |
|---|---|---|
| 5 000 | 2.60 秒 | 0.003 秒 |
| 10 000 | 5.30 秒 | 0.004 秒 |
| 20 000 | 10.6 秒 | 0.005 秒 |
逐个试的复杂度是 O(答案范围 × n)。
「答案范围」由数值大小决定，不是由 n 决定。 数值都是个位数的话，答案范围只有几十，暴力一下就试完了； 数值上到十万，答案范围就是几十万。
所以 genBig.cpp 里特意把数值造到 100000。
造数据要打在暴力的痛点上 —— 这句话这本教材里已经说第三遍了，
因为它是真的重要。
6 ★ 关键的一步：可行性是单调的
把每个候选答案的可行性列出来，你会看到这个形状：
上限: 10 11 12 13 14 15 16 17 ... 35
可行: ✗ ✗ ✗ ✗ ✓ ✓ ✓ ✓ ... ✓
↑
我们要的答案✗ 全在左边，✓ 全在右边，中间只有一条分界线。
为什么一定是这个形状？因为上限放宽了只会更容易： 如果上限 14 能切成 3 段，那上限 15 用同样的切法当然也行。 所以「可行」这个性质一旦成立，就对更大的值全部成立。
这正是第 8 章说的二分的真正条件：不是「有序」，是「存在分界点」。
于是第 8 章那个模板原封不动搬过来，只把 check 换成 ok：
long long l = 最大的那个数, r = 所有数之和;
while (l < r) {
long long mid = l + (r - l) / 2;
if (ok(mid)) r = mid; // 可行 → 答案不会更大
else l = mid + 1; // 不可行 → 答案只能更大
}
// l 就是答案O(n log sum)。sum 就算是 10¹⁴，log 也只有 47 —— 验证 47 次就完事了。
下界写小了、上界写大了都没关系（只是多几轮），但不能漏掉真正的答案。
- 下界写成 0 或 1？可以，只是浪费几轮。
- 下界写成
sum / m（看着挺聪明）？危险 —— 万一某个数比它还大，答案就在范围外面了。 - 上界写成
sum？稳。写成别的「感觉够大」的值？出事了都不知道为什么。
拿不准就把范围放宽。 log 的代价小到可以忽略，漏掉答案的代价是 0 分。
7 正解
点「运行 ▶」看结果
把它和 brute.cpp 并排看：ok() 函数一个字都没改。
变的只有「怎么找那个答案」—— 从「一个一个试」变成「二分着试」。
点「运行 ▶」看结果
8 单步看「猜 → 验证 → 缩小范围」
- 上面那条数轴是所有候选答案。每验证一个就盖上 ✓ 或 ✗。
- 下面画的是当前猜测下贪心切出来的分段，以及用了几段。
- 播完之后回头看数轴：红的全在左、绿的全在右。这个形状就是二分的许可证。
试试这两个极端：
- 把
m改成1—— 只能分一段，数轴上只有最右边那一格是 ✓。 - 把
m改成10（比数列还长）—— 几乎整条数轴都是 ✓，答案就是最大的那个数。
9 ★ 对拍：两种，都要做
把「二分」那一栏换成你自己默写的，再点开始。
标准答案是「逐个试」的暴力 —— 它和你的二分共用同一个 ok()，
所以这一轮对拍验的是二分的边界写对没有。
brute.cpp 和 fast.cpp 共用同一个 ok() 函数。
也就是说，如果那个贪心 ok() 本身就是错的，两份程序会一起错 ——
输出当然一致，对拍全过，你还以为自己写对了。
这是对拍最容易被忽略的陷阱：两个错得一模一样的程序，是对不出问题的。
所以我们再写一份 动态规划版本 —— 它不依赖任何贪心，
把所有切法都考虑了一遍（f[i][j] = 前 i 个数分成 j 段的最优解）。
慢是慢（O(n²m)），但它和贪心思路完全不同，能真正验证 ok() 是对的。
对拍的标准答案，最好是用完全不同的思路写出来的。
同一个思路写两遍，只能验出打字错误； 不同思路写两遍，才能验出想法错误。
这条经验会跟着你一辈子 —— 它不只适用于算法竞赛。
10 套路总结：怎么认出「这题要二分答案」
- 题目问的是「最大值最小」「最小值最大」「最多/最少能怎样」。
- 直接求最优解很难，但「给定一个值，判断能不能达到」很容易。
- 这个判断是单调的：值放宽了就更容易满足（或反过来）。
三条都对上，就套模板：
l = 答案下界, r = 答案上界;
while (l < r) {
mid = l + (r - l) / 2;
if (check(mid)) r = mid; // 求「最小的可行值」
else l = mid + 1;
}求「最大的可行值」怎么办？ 最省事的办法是把问题反过来定义 check，仍然用这一个模板 —— 不要去记第二套「上取整 + l = mid」的写法，那正是第 8 章说的混搭翻车现场。
| 题目怎么说 | check 是什么 |
|---|---|
| 分成 m 段，最大段和最小 | 贪心分段，数段数（本章） |
| 砍树取够 M 米，锯片最高多少 | 按高度砍一遍，累加木材量 |
| 移走 M 块石头，最小跳跃距离最大 | 贪心移石头，数移了几块 |
| n 头牛放进畜栏，最小间距最大 | 贪心放牛，数放了几头 |
| 第 k 小的数是多少 | 数一数「不超过 x 的有几个」 |
全都是同一个模板 + 一个不同的 check。check 才是每道题的真正内容。
11 自测
- 洛谷 P1182 数列分段 Section II —— 本章原题。必须一次写对
- 洛谷 P1873 砍树 —— 入门二分答案。check 是「按这个高度砍，能得到多少木材」
- 洛谷 P2678 跳石头 —— NOIP2015。最小值最大化，check 是贪心地数「要移走几块石头」
- 洛谷 P1024 一元三次方程求解 —— NOIP2001。实数二分，终止条件要用精度（while (r - l > 1e-6)）而不是 l < r
五章走完，你手上多了五个零件：枚举与模拟、前缀和与差分、 双指针、二分查找、二分答案。
它们会作为骨架出现在后面几乎每一道题里。
下一站是阶段 2（排序与分治）。第 10 章会从冒泡讲到归并再到快排 —— 而归并排序正是第 11 章「分治」的载体，也是第 2 章「大问题 = 小问题 + 一步真活 + 小问题」 最标准的一次现身。