二分答案入门：从P1182数列分段理解最大值最小

如果你刚开始刷二分答案洛谷P1182 数列分段 Section II几乎是绕不开的一道题。它的名气不在代码量——完整实现不超过三十行——而在于第一次见到最大值最小这种问法时大多数人会先懵一会儿。我第一次做这道题时脑子里瞬间蹦出两个方案动态规划和一个自以为聪明的贪心结果一个被数据范围直接劝退另一个被反例当场打脸。这篇文章我会完整讲清楚从题目理解、为什么直觉方案不靠谱、二分答案里的check函数怎么写、有哪些边界坑再到同名的CCF CSP数列分段和一系列二分答案变体。最大值最小这四个字如果第一次见确实抽象但一旦你从猜一个上限然后验证它的角度去看它就会变成一类极其顺手的问题。这篇文章适合刚学完二分查找想进阶的读者也适合准备算法竞赛或面试时需要快速过一遍二分答案模板的人。1. 题目到底在求什么每段和的上限而不是段数1.1 先用手算把一个例子吃透题干很短给定一个长度为N的正整数数列要把它切成M段每段必须是连续子串问每段和的最大值最小可能是多少。注意三个关键点。第一切出来的每一段都是原数列的连续部分不是随便挑几个数凑成一段第二段数固定是M第三优化的目标不是让每段尽量平均而是让最重的那一段尽量轻。很多题解把最大值最小挂在嘴边但如果你没见过这类题这四个字确实很飘。别急手算一个例子就清楚了。数列1 2 3 4 5M3。把所有合法三段切法列出来看各自最重的一段1 | 2 3 | 4 5段和1、5、9最大91 2 | 3 | 4 5段和3、3、9最大91 2 | 3 4 | 5段和3、7、5最大71 2 3 | 4 | 5段和6、4、5最大61 | 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(k1, i)) )意思是前k个数分成j-1段第j段是k1到i取前j-1段的最大段和和最后一段和两者中较大的那个作为分成j段的临时答案然后对所有k取最小。这个转移本身完全正确配合前缀和可以O(1)算出任意区间和。问题是时间复杂度是O(N²M)。N稍微上到10^5N²直接就是10^10再乘M哪怕M很小也完全跑不动。滚动数组能省空间但省不了时间这是硬伤。所以P1182最核心的约束不是不够优雅而是DP在这个数据范围下根本没有活路。它逼迫你跳出逐段规划的思维换一个更高效的判断方式。2.2 现场贪心的反例直觉是怎么翻车的还有一种看起来很合理的贪心方向让每段和尽量接近sum/M或者说能塞就塞差不多就切。先说能塞就塞它其实等价于P1181的贪心但问题是那需要先知道一个目标上限而这个上限恰好就是本题要求的东西这就成了循环论证。那塞到差不多就切这种启发式呢比如设目标Tceil(sum/M)每段累加到接近T就切开。听起来挺美但它没有保证。举个反例数列1 1 1 8 8M2sum19T≈10。从左往右塞1113再加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 mcnt初始值是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变成c1而每段的和只会变小不可能超过x。反复拆下去总能拆到正好m段——前提是m不超过n因为最多能拆成n段每段一个数。反过来如果贪心这种最优切法都需要超过m段那任何方案都至少需要这么多段x就不可行。所以最多不超过m段和能分成恰好m段且每段和不超过x在这题里是等价的。check写而不是是整个判定问题成立的关键修正。每次有朋友问我这题为什么不是cntm我都会让他先想清楚上面这个拆段逻辑。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更大所以rmid不可行说明mid太小答案至少是mid1所以lmid1。这个模板很稳后面套其他二分答案题我都会直接用。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和mPython的函数调用虽然不如C快但二分总共只有几十轮每轮O(N)N10^5时完全够用实测不会有压力。4.3 用开头的例子完整走一遍二分拿文章开头的例子1 2 3 4 5M3来手推一次二分能更直观看到收敛过程。初始l5r15。mid10check(10)1234刚好等于10切一段剩5单独一段cnt2≤3可行r10mid7check(7)1236再加4超7切一段459再切一段cnt3≤3可行r7mid6check(6)123645这段和是9超6再切cnt3≤3可行r6mid5check(5)12336超5切一段347超5切一段459超5再切cnt43不可行l6此时lr6循环结束输出6。可以看到二分的过程就是在可行和不可行之间反复逼近分界线最后一轮l和r相遇的位置就是答案。4.4 五处细节每一个都可能让你WA坑一左边界l必须从max(a)开始。如果从0开始小x全部不可行最终也能收敛到正确答案但会让check在大量无效区间里空转而且逻辑上不够硬。更根本的原因是x连单个元素都装不下时任何切法都不可能满足条件lmax(a)直接砍掉了整个无解区间。坑二右边界r必须取sum(a)。所有数放一段时最大段和就是总和答案不可能超过它。有人喜欢把r随手设成1e9或某个大数多数情况能过但一旦总和超过这个数就悄悄WA了。坑三看到N到10^5就长点心int会爆。mid、cur、r全都得开long long。这题不少WA不是思路问题而是心里想着好像数不大结果总和轻轻松松超过2^31-1。坑四二分模板必须和取整方式配套。上面用的是闭区间[l, r] mid(lr)1 可行时rmid 不可行时lmid1。不要手滑改成lmidlmid在区间长度为2时mid永远等于ll就缩不动了死循环。如果你习惯用(lr1)1那配套的就是rmid-1、lmid两条路线都能通别混着用。坑五cnt初始值是1不是0。因为从第一段就开始计数了。初始化为0会让check整体少算一段在m恰好卡在临界值时结果直接出错。同样的cur要清0。还有一个自测技巧交之前用mn和m1两个极端用例验证。mn时答案一定是max(a)每个数单独一段m1时答案一定是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; vectorint 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给定段数求最小最大段和贪心扫描统计最少段数返回cntmP2678 跳石头最大化最短跳跃距离模拟移除石头若移除数M则可行P1824 进击的奶牛最大化最近的两头牛距离贪心安排牛棚判断能否放下m头P1873 砍树最大化刀片高度使砍下木材M遍历树高累加砍下木材量这些题刷下来你大概率会对给一个候选答案用贪心验证这个模式形成肌肉记忆。再看到最大值最小的问法第一反应就不再是纠结怎么排序怎么切而是先问自己check函数怎么写我个人的习惯是遇到这类题先把check函数单独拎出来写干净再套二分模板。P1182是我见过最适合用来建立二分答案直觉的题之一它把两层东西拆得很清楚外层二分负责猜答案内层贪心负责验证。一旦你接受这个拆法往后刷跳石头、刷砍树都会觉得顺理成章。