如果你刚开始刷二分答案，洛谷P1182 数列分段 Section II几乎是绕不开的一道题。它的名气不在代码量——完整实现不超过三十行——而在于第一次见到"最大值最小"这种问法时，大多数人会先懵一会儿。我第一次做这道题时，脑子里瞬间蹦出两个方案：动态规划和一个自以为聪明的贪心，结果一个被数据范围直接劝退，另一个被反例当场打脸。
这篇文章我会完整讲清楚从题目理解、为什么直觉方案不靠谱、二分答案里的check函数怎么写、有哪些边界坑，再到同名的CCF CSP数列分段和一系列二分答案变体。"最大值最小"这四个字如果第一次见，确实抽象，但一旦你从"猜一个上限，然后验证它"的角度去看，它就会变成一类极其顺手的问题。这篇文章适合刚学完二分查找想进阶的读者，也适合准备算法竞赛或面试时需要快速过一遍二分答案模板的人。
1. 题目到底在求什么：每段和的上限，而不是段数
1.1 先用手算把一个例子吃透
题干很短：给定一个长度为N的正整数数列，要把它切成M段，每段必须是连续子串，问"每段和的最大值"最小可能是多少。
注意三个关键点。第一，切出来的每一段都是原数列的连续部分，不是随便挑几个数凑成一段；第二，段数固定是M；第三，优化的目标不是"让每段尽量平均"，而是"让最重的那一段尽量轻"。很多题解把"最大值最小"挂在嘴边，但如果你没见过这类题，这四个字确实很飘。别急，手算一个例子就清楚了。
数列：1 2 3 4 5，M=3。
把所有合法三段切法列出来，看各自最重的一段：
- 1 | 2 3 | 4 5：段和1、5、9，最大9
- 1 2 | 3 | 4 5：段和3、3、9，最大9
- 1 2 | 3 4 | 5：段和3、7、5，最大7
- 1 2 3 | 4 | 5：段和6、4、5，最大6
- 1 | 2 3 4 | 5：段和1、9、5，最大9
所以这个例子的答案是6，对应切法1 2 3 | 4 | 5。虽然只是一个小小的手算，但已经能看出一个很重要的性质：答案一定落在[max(A), sum(A)]这个区间里。它不可能小于最大的那个单元素，因为任何一段至少要装一个数；也不可能大于所有数之和，因为把所有数放在一段时，最大段和就是总和。这两个端点，就是后面二分时的下界和上界，先记住结论。
1.2 Section I 和 Section II 的区别
P1182有个姊妹题，P1181 数列分段 Section I。Section I的问法是：给定每段和的上限M，求最少能分成几段。解法很直白：从左往右累加，超过M就新开一段，一次扫描完事。
Section II等于把问题反过来了：给定段数M，反推那个最重的段最小能是多少。Section I的贪心能一步到位，是因为"上限"已经给定了；Section II里上限未知，你没法直接贪——因为你根本不知道应该拿什么数去和当前段累计和比较。
把这两个题并排看，是理解二分答案最好的入口。"给定一个限制，求最优结果"往往可以用贪心；"求一个最优的限制"才是二分答案的典型主场。
2. 直接DP和现场贪心，为什么两条路都走不通
2.1 DP的思路：状态清晰，复杂度劝退
如果没接触过二分答案，看到"分成M段，让某指标最小"，第一反应大概率是动态规划。设dp[i][j]表示前i个数分成j段时，最大段和的最小值。转移时枚举最后一段从哪里开始：
dp[i][j] = min over k ( max(dp[k][j-1], sum(k+1, i)) )
意思是前k个数分成j-1段，第j段是k+1到i，取"前j-1段的最大段和"和"最后一段和"两者中较大的那个，作为分成j段的临时答案，然后对所有k取最小。
这个转移本身完全正确，配合前缀和可以O(1)算出任意区间和。问题是时间复杂度是O(N²M)。N稍微上到10^5，N²直接就是10^10，再乘M，哪怕M很小也完全跑不动。滚动数组能省空间，但省不了时间，这是硬伤。
所以P1182最核心的约束不是"不够优雅"，而是DP在这个数据范围下根本没有活路。它逼迫你跳出逐段规划的思维，换一个更高效的判断方式。
2.2 现场贪心的反例：直觉是怎么翻车的
还有一种看起来很合理的贪心方向：让每段和尽量接近sum/M，或者说"能塞就塞，差不多就切"。先说"能塞就塞"，它其实等价于P1181的贪心，但问题是那需要先知道一个"目标上限"，而这个上限恰好就是本题要求的东西，这就成了循环论证。
那"塞到差不多就切"这种启发式呢？比如设目标T=ceil(sum/M)，每段累加到接近T就切开。听起来挺美，但它没有保证。举个反例：数列1 1 1 8 8，M=2，sum=19，T≈10。从左往右塞，1+1+1=3，再加8变成11超过T，于是切出第一段1 1 1（和3），剩下8 8（和16），答案16。但最优切法是1 1 1 8 | 8，段和13和8，答案是13。启发式直接给出了错误答案。
这类反例想说明一件事：没有一个简单的"现场目标"能让你一步贪心命中答案。如果上限已知，贪心扫描确实能给出最少段数；但上限未知时，你根本没法判断当前这一刀该不该切。这个观察恰好指向真正的突破口——把答案当成一个可以猜的数。先猜一个上限x，再验证"每段和不超过x时，能不能用不超过M段装完所有数"。验证过程用贪心，猜答案的过程用二分。两个工具一拼，问题就拆开了。
3. 猜一个上限X，再用贪心验证它可不可行
3.1 验证函数check(x)的写法
假设我们猜了一个上限x，怎么判断它可不可行？方法就是Section I那套贪心：从左到右累加，只要加上当前数后段和不超过x，就继续往当前段里放；一旦超过x，说明这一段已经装不下了，必须在这里切一刀，新开一段装当前这个数。
写成伪代码就是：
cnt = 1 cur = 0 for v in a: if cur + v > x: cnt = cnt + 1 cur = v else: cur = cur + v return cnt <= m
cnt初始值是1，因为至少有一段；cur是当前段正在累计的和。注意"超了就切"的判断发生在把v加入之前，不要让v硬塞进当前段再切，那样语义就乱了。
这个check函数本身很简单，但它回答的已经不是"最大值最小是多少"，而是"如果我认为答案是x，到底成不成立"。这一步把最优化问题变成了判定问题，这是二分答案所有题目的共同套路。
3.2 为什么这个贪心能得到"最少段数"
有人会问：这个贪心的切法，凭什么就是段数最少的切法？万一切早了一刀，后面反而多切几刀怎么办？
答案是：这种"尽量往后延"的贪心，任何一次切分都不会让后续变得更难。你可以把任意一种可行切法和贪心切法并排比较：贪心的第一段结束位置，一定不早于其他方案第一段的结束位置，因为它是"在不超过x的前提下能延伸的最远位置"。第一段延伸得更远，意味着留给第二段的元素更少或相同，第二段只会更轻松。这样逐段看下去，贪心的每一段都不会比其他方案更早结束，所以总段数不会比任何方案多。
这个直观说法虽然不完全是形式化证明，但在算法理解层面已经够用了。真要在竞赛题解里较真，可以用反证：若存在总段数更少的方案，把它第一段的右端点换成贪心方案的右端点，后面的每一段可容纳的剩余序列只会更短，不可能需要更多段，从而矛盾。不管用哪种说法，结论一致：check里贪心扫描段数，就是在"每段和不超过x"条件下能达到的最少段数。
3.3 为什么是 cnt <= m，而不是 cnt == m
这是P1182上最容易被问住的细节。题目明明要求分成恰好M段，你check返回的却是cnt <= m，这不是放宽了条件吗？
并没有。如果某个x用贪心只需要c段就能装完，而且c < m，我们只需要把其中任意一段拆开。比如在段内随便找个位置切一刀，段数就从c变成c+1，而每段的和只会变小，不可能超过x。反复拆下去，总能拆到正好m段——前提是m不超过n，因为最多能拆成n段，每段一个数。反过来，如果贪心这种"最优切法"都需要超过m段，那任何方案都至少需要这么多段，x就不可行。
所以"最多不超过m段"和"能分成恰好m段且每段和不超过x"，在这题里是等价的。check写<=而不是==，是整个判定问题成立的关键修正。每次有朋友问我这题为什么不是cnt==m，我都会让他先想清楚上面这个拆段逻辑。
4. 完整代码与五个防不胜防的边界坑
4.1 C++ 实现
这里给出一个可以直接提交的C++版本。上下界和二分模板我都按最常见的写法处理。
#include <bits/stdc++.h> using namespace std; int n, m; long long a[100005]; bool check(long long x) { int cnt = 1; long long cur = 0; for (int i = 1; i <= n; i++) { if (cur + a[i] > x) { cnt++; cur = a[i]; } else { cur += a[i]; } } return cnt <= m; } int main() { scanf("%d%d", &n, &m); long long l = 0, r = 0; for (int i = 1; i <= n; i++) { scanf("%lld", &a[i]); l = max(l, a[i]); r += a[i]; } while (l < r) { long long mid = (l + r) >> 1; if (check(mid)) r = mid; else l = mid + 1; } printf("%lld\n", l); return 0; }l初始化为max(a)，r初始化为sum(a)。check(mid)为true时，说明mid这个上限可行，答案不会比mid更大，所以r=mid；不可行说明mid太小，答案至少是mid+1，所以l=mid+1。这个模板很稳，后面套其他二分答案题我都会直接用。
4.2 Python 实现与IO注意点
Python版本也很短，但IO一定要用buffer一次性读入，否则N到10^5时，input()逐行读会慢到让你怀疑人生。
import sys def main(): data = list(map(int, sys.stdin.buffer.read().split())) n, m = data[0], data[1] a = data[2:] left, right = max(a), sum(a) def check(x): cnt = 1 cur = 0 for v in a: if cur + v > x: cnt += 1 cur = v else: cur += v return cnt <= m while left < right: mid = (left + right) // 2 if check(mid): right = mid else: left = mid + 1 print(left) main()这里check里闭包捕获了a和m，Python的函数调用虽然不如C++快，但二分总共只有几十轮，每轮O(N)，N=10^5时完全够用，实测不会有压力。
4.3 用开头的例子完整走一遍二分
拿文章开头的例子1 2 3 4 5，M=3来手推一次二分，能更直观看到收敛过程。初始l=5，r=15。
- mid=10：check(10)，1+2+3+4刚好等于10切一段，剩5单独一段，cnt=2≤3，可行，r=10
- mid=7：check(7)，1+2+3=6，再加4超7切一段，4+5=9再切一段，cnt=3≤3，可行，r=7
- mid=6：check(6)，1+2+3=6，4+5这段和是9超6再切，cnt=3≤3，可行，r=6
- mid=5：check(5)，1+2=3，+3=6超5切一段，3+4=7超5切一段，4+5=9超5再切，cnt=4>3，不可行，l=6
此时l=r=6，循环结束，输出6。可以看到，二分的过程就是在"可行"和"不可行"之间反复逼近分界线，最后一轮l和r相遇的位置就是答案。
4.4 五处细节：每一个都可能让你WA
坑一：左边界l必须从max(a)开始。如果从0开始，小x全部不可行，最终也能收敛到正确答案，但会让check在大量无效区间里空转，而且逻辑上不够硬。更根本的原因是，x连单个元素都装不下时，任何切法都不可能满足条件，l=max(a)直接砍掉了整个无解区间。
坑二：右边界r必须取sum(a)。所有数放一段时，最大段和就是总和，答案不可能超过它。有人喜欢把r随手设成1e9或某个大数，多数情况能过，但一旦总和超过这个数就悄悄WA了。
坑三：看到N到10^5就长点心，int会爆。mid、cur、r全都得开long long。这题不少WA不是思路问题，而是心里想着"好像数不大"，结果总和轻轻松松超过2^31-1。
坑四：二分模板必须和取整方式配套。上面用的是闭区间[l, r] + mid=(l+r)>>1 + 可行时r=mid + 不可行时l=mid+1。不要手滑改成l=mid，l=mid在区间长度为2时mid永远等于l，l就缩不动了，死循环。如果你习惯用(l+r+1)>>1，那配套的就是r=mid-1、l=mid，两条路线都能通，别混着用。
坑五：cnt初始值是1，不是0。因为从第一段就开始计数了。初始化为0会让check整体少算一段，在m恰好卡在临界值时结果直接出错。同样的，cur要清0。
还有一个自测技巧：交之前用m=n和m=1两个极端用例验证。m=n时答案一定是max(a)，每个数单独一段；m=1时答案一定是sum(a)，所有数放一起。这两个用例能过，代码基本就稳了。
5. 从P1182到CSP数列分段：同类题的识别与延伸
5.1 同名但截然不同的CSP数列分段
如果你用"数列分段"作为关键词搜索，很可能会翻到另一个同名题：CCF CSP认证里的201509-1 数列分段。那题问的是：给定一个整数序列，把连续且值相同的元素划为一段，统计共有几段。
比如序列1 2 2 3 3 3 1，切法是1 | 2 2 | 3 3 3 | 1，一共4段。做法就是一次遍历：答案初始为1，从第二个元素开始，每碰到一个和上一个不同的数，ans就加1。
#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<int> a(n); int ans = 1; for (int i = 0; i < n; i++) { cin >> a[i]; if (i > 0 && a[i] != a[i - 1]) ans++; } cout << ans << endl; return 0; }这题和P1182虽然都叫"数列分段"，但一个是计数题，一个是二分答案题，思路完全不同，纯属名字撞车。用关键词搜题解时一定要先看清题号，不然很容易浪费时间看错题。
5.2 二分答案题目的通用识别标志
P1182只是二分答案大家族里的一员，它身上有三个很典型的识别标志，你可以在其他题目里反复验证：
- 题干出现"最大值最小"或"最小值最大"，或者等价地要求"某种上限尽量小"；
- 答案具有单调性：x越大，可行性越容易成立，这是二分的前提；
- 直接枚举所有方案或直接DP复杂度不可接受，但"给你一个候选答案，验证它可不可行"这件事很简单。
满足这三点的题，思路就是先写check函数，再套二分模板。check函数往往配合贪心，因为"给定限制之后求最优"通常有贪心解，而"求那个最优的限制"恰恰是二分要做的事。P1182的check用的是P1181的贪心，跳石头的check是模拟移除石头，进击的奶牛的check是贪心安排牛的位置——同一个套路，换了不同的判定逻辑而已。
5.3 一套可以接着刷的题单
如果你做完P1182还想巩固，下面这几个题都很值得刷，问法和check各异，但骨架完全一样。
| 题号 | 问题本质 | check函数做法 |
|---|---|---|
| P1181 数列分段 Section I | 给定每段上限，求最少段数 | 直接贪心扫描，不用二分 |
| P1182 数列分段 Section II | 给定段数，求最小最大段和 | 贪心扫描统计最少段数，返回cnt<=m |
| P2678 跳石头 | 最大化最短跳跃距离 | 模拟移除石头，若移除数<=M则可行 |
| P1824 进击的奶牛 | 最大化最近的两头牛距离 | 贪心安排牛棚，判断能否放下m头 |
| P1873 砍树 | 最大化刀片高度，使砍下木材>=M | 遍历树高累加砍下木材量 |
这些题刷下来，你大概率会对"给一个候选答案，用贪心验证"这个模式形成肌肉记忆。再看到"最大值最小"的问法，第一反应就不再是纠结怎么排序怎么切，而是先问自己：check函数怎么写？
我个人的习惯是，遇到这类题先把check函数单独拎出来写干净，再套二分模板。P1182是我见过最适合用来建立二分答案直觉的题之一，它把两层东西拆得很清楚：外层二分负责猜答案，内层贪心负责验证。一旦你接受这个拆法，往后刷跳石头、刷砍树，都会觉得顺理成章。
