数列分段II：二分答案+贪心校验解决最大值最小化

1. 题目到底在考什么一句不说破的“最大值最小化”第一次见到“1436数列分段II”的选手多数会先松一口气数组、分段、求和这不是模拟题吗真上手写贪心才发现怎么分都差一点写DP又发现n的范围根本扛不住。这道题真正想考的不是“你会不会分段”而是你懂不懂一类非常经典的优化模型——最大值最小化Minimize the Maximum。说人话就是给你一个数组要求切成M段每段连续问怎么切能让“所有段里和最大的一段”尽可能小。这道题在信息学竞赛里属于二分答案 贪心校验的入门必刷题也是后面所有“可行性判断类二分”题目的敲门砖。很多同学学到树状数组、线段树、DP优化之后回头再看它反而有一种“原来地基在这里”的感觉。它适合刚学完二分查找、想要进阶到二分答案的初学者也适合准备省选、用来复习“二分边界处理”的老选手。如果你能把这道题的边界、校验、贪心细节讲清楚那二分答案这一整个题型你基本就算吃透了。我为什么说它是“地基”因为后续你会遇到大量题目长得完全不一样——有的让你分书、有的让你运货、有的让你调度任务——但剥掉外壳核心全是“给一个答案X快速判断能不能行”而判断的标准往往就是一次线性的贪心扫描。1436就是这个模型的干净版本没有任何额外的数据结构干扰纯粹考二分和贪心本身。2. 为什么暴力不行从“枚举分段”到“枚举答案”的思维转变2.1 先看看朴素的思路坑在哪拿到这道题第一反应一般是枚举所有分段方案找到和最大值最小的那个。数组分成M段等价于在n-1个缝隙里选M-1个位置放隔板组合数是C(n-1, M-1)。当n100000M100000时这个数是天文数字连枚举到宇宙热寂都算不完。哪怕n只有1000M有50组合数也早就爆炸了。那DP呢设f[i][j]表示前i个数分成j段的和最大值最小值状态转移需要枚举最后一段的起点k计算k到i的和。状态数O(nM)转移O(n)总复杂度O(n²M)。当n、M都到10^5级别时这个复杂度同样是完全不可行的。DP虽然能“在没有头绪时保证正确”但它解决不了这道题的大数据范围。这里有个很重要的思维定势要打破当“枚举方案”走不通时换个方向——枚举答案。我们不去纠结“怎么切”而是先问“如果要求每段和都不超过X能不能切出来M段”然后去二分这个X。这就是二分答案的核心逻辑。2.2 把“最优解”转化为“可行解”的验证问题二分答案的第一性原理是如果你能快速回答“某个值X是不是可行”并且这个可行性随X单调变化那就能用二分把最优解找出来。在这道题里“每段和的最大值不超过X”这个条件随X增大可行性只增不减——X越大分段越不容易超限当然越容易满足。单调性成立二分就合法。于是问题被拆成两部分二分X的值域确定搜索范围。对每个X用贪心从左到右扫一遍数组验证“能否在每段和≤X的限制下把整个数组分成不超过M段”。注意这里的关键词是“不超过M段”。很多人纠结“为什么不是恰好M段”这是个极其重要的细节。如果能在每段和≤X的限制下分成少于M段那一定可以再拆出M段吗答案是肯定的你把其中一些段再拆开每段的和只会更小一定仍然满足≤X。所以“不超过M段”和“恰好M段”在这里是等价的判断条件。贪心时我们只统计最少能分成多少段然后看它是否≤M就够了。这个“改为验证可行性再二分”的思路其实生活里特别常见。比如你想知道一笔预算能买多少斤苹果不会挨个试所有购买组合而是先猜一个单价上限再看一斤一斤能不能买够。把“最优问题”变成“判定问题”复杂度往往降一个量级。3. 二分边界怎么取不踩死循环的完整推导3.1 左边界、右边界、答案是开区间还是闭区间边界是二分答案题里最容易翻车的地方很多人样例过了、一交题就TLE或者死循环基本都是边界没理清。这道题的值域非常明确下界L所有段里至少有一段要包含数组里最大的那个元素所以每段和的最小可能值不可能小于数组中的最大值。取L max(a[i])。上界R最极端的情况是整段不分直接一段装下所有数那每段和就是数组总和。取R sum(a[i])。也就是说答案X一定落在[max(ai), sum(ai)]这个闭区间里。用二分查找在这个区间里找“第一个可行值”就是我们要求的最小值。这是典型的“可行域连续且左端不可行、右端可行”的单调序列问题比答案小的值全都不可行答案本身及以后全都可行。我用的是“闭区间二分”写法循环条件是 while (L R)每次取 mid (L R) / 2。如果mid可行说明答案在左半边包括mid自己移动右边界R mid如果mid不可行说明答案在右半边移动左边界L mid 1。当L R时这个点就是最小可行值。这段逻辑很多人会记混我建议死记一句口诀“可行往左靠不可行往右跳”。3.2 用数据算一遍你就懂了拿一个经典样例来走一遍流程数组为 [4, 2, 4, 5, 1]要分成3段。第一步算边界max 5sum 16所以搜索范围是[5, 16]。取mid (5 16) / 2 10。用贪心验证426没超10410刚好没超5就超了所以第一段到第3个数为止和是10剩下516共2段。段数2 ≤ 3说明10可行。答案可能是10甚至更小把R缩到10。再取mid (5 10) / 2 7。验证426没超7410超了第一段到第2个数和是6下一段459超了所以单独4一段再516一段。一共3段3 ≤ 3说明7也可行。R缩到7。再取mid (5 7) / 2 6。验证426刚好没超410超了第一段是前两个数第二段459超了单独4一段第三段516。段数是3但你会发现这里出了问题第二段单独一个4它自身不超过6没问题可后面516也没问题一共3段好像可行等等4这个数比6小它分段后每段都≤6吗问题出在第三段516没超但第一段6也没超第二段4也没超。这样看6也可行再仔细验证42645不对数组顺序是4,2,4,5,1。从头扫累积s0s44≤6累积s4s26≤6累积s6s4106切段新段累积s4s596切段新段累积s5s16≤6。段数统计第一段[4,2]第二段[4]第三段[5,1]一共3段而且每段和分别是6、4、6都≤6。诶那6也是可行的但直觉告诉我们数组最大值是5把5放哪一段那一段和至少是5而每段和最大是6好像确实有可能可原题样例的答案是6吗不是的这题的标准答案应该是6我们再检查一下分成3段段和最大最小我们可以分成[4,2]、[4]、[5,1]段和是6、4、6最大值6。如果要求最大值5呢5就必须单独成段或和其他数组合但4? 任何包含5的一段和至少是5同时数组里的1、2、4、4还需要安排每段和不超过5的话426超了4只能单独一段2也只能和1组合成3但加上4单独、5单独——总共需要4段。所以5不可行最小可行值是6。上面二分到mid6时验证确实是3段所以答案就不会再变小了R6循环结束答案就是6。这里我再强调一遍mid7的时候就已经可行了但二分要继续压缩直到找到最小的可行值6整个过程退出时LR6。这个手算过程值得你亲自走一遍因为二分题的调试全靠这种“人工模拟二分”的能力。你只要把每一步的L、R、mid、可行性列成一个表很多鬼迷日眼的错误立刻就能暴露。4. 核心代码实现与细节写对check函数才是王道4.1 完整可AC的C参考代码下面这份代码是我调试过多次的最终版本可以直接提交通过。注意几个关键细节我写完了再逐个解释。#include bits/stdc.h using namespace std; const int MAXN 100005; int a[MAXN]; int n, m; // check函数判断“每段和都不超过limit”时能否分成不超过m段 bool check(int limit) { int cnt 1; // 当前已经使用的段数至少1段 long long sum 0; // 当前这一段累积的和 for (int i 1; i n; i) { // 单个元素超过limit直接返回false防御性判断 if (a[i] limit) return false; if (sum a[i] limit) { cnt; // 需要另起新段 sum a[i]; // 新段从当前元素开始 } else { sum 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(%d, a[i]); if (a[i] L) L a[i]; // 下界取最大值 R a[i]; // 上界取总和 } while (L R) { long long mid (L R) / 2; if (check(mid)) R mid; // 可行尝试更小的值 else L mid 1; // 不可行答案必定更大 } printf(%lld\n, L); return 0; }这段代码的check函数看着简单但有两个地方特别容易出问题。我之前带过不少同学十个里有六七个第一次写的版本会在这里卡住下面一条条说清楚。4.2 check函数里的两个关键陷阱第一个陷阱cnt初始值必须是1而不是0。整个数组至少要分成一段。如果你让cnt0然后在遍历中“遇到超限才切段”那最后的半截数组不会被计入段数会导致段数偏少。比如数组[4,2,4,5,1]limit10时如果cnt0扫描中切了两刀得到3段但最后一段[5,1]没有被统计你只数到2段判断结果就不对了。正确写法是cnt1代表从一开始就有第一段在“累积中”。第二个陷阱else分支里必须直接sum a[i]而不是sum a[i]。很多人为了避免“段和重新开始”的歧义写成每次遇到超限就cnt并让suma[i]然后在下一轮继续加。逻辑上这种写法也能work但有一个边界错误很隐蔽如果当前元素a[i]本身已经大于limit你把它当作新一段的起点然后下一轮发现suma[i1]超过limit表面上好像没问题但“单个元素超过limit”的情况应该直接被判定为不可行。因为如果某一段只有一个元素就已经超过limit你再怎么分都不可能让这一段的max不超过limit。虽然题目数据一般不会出现这种元素因为下界取max后limit始终≥max(a[i])但作为一个健壮性检查写进check里能让你的代码更稳。4.3 为什么必须用long long而不是int这个坑是最不起眼、但最容易让人捶桌子的。n最大10^5每个a[i]最大10^4总和是10^9刚好卡在int的边界附近int最大约21.47亿。如果数组再长一点或者数据再强一点int直接溢出变负数你的二分范围就彻底乱套有时候跑出死循环有时候输出一个莫名其妙的负数。我建议所有跟数组总和相关的变量一律用long long包括L、R、mid、sum不要心疼那点内存比赛里你永远不知道出题人会不会把数据范围偷偷加到极限。另外注意一个常被忽略的点用scanf/printf而不是cin/cout在这个数据规模下其实差距不大但很多老牌OJ的评测环境不稳定用scanf能少一点无谓的输入耗时。当然如果你用 cin 并且关了同步也没问题看个人习惯。4.4 retur cnt m 这个条件到底在判断什么我再把这个条件掰开讲一遍。二分过程中我们不断尝试某个limit值。check(limit)做的事是在每段和都不超过limit的前提下用贪心策略贪出“最少能分多少段”。这个“最少段数”如果比要求的m还少说明什么呢说明限制条件不够紧我们可以把某些段再拆开最终拆到正好m段而且拆开后每段的和只会更小依然不会超过limit。所以cnt ≤ m就等价于“能做到分成恰好m段且每段和≤limit”。反过来如果cnt都比m大了说明这个limit限制下已经不得不超过m段了那无论如何都没法满足要求返回false。这里引入的贪心其实是“每次尽量多装直到装不下再开新段”。为什么这个贪心是对的因为你要在限制下让段数尽量少那每一段当然要尽量“装得更满”。你可能会想有时候少装一个元素、让后面的元素把后面的段凑得更均匀会不会反而减少总段数实际上不会。因为每段和的上限都一样尽早把当前段装满只是把后面元素往后推不会让后面产生额外更多的段而如果你早开新段只会白白增加一段的总数。这个“能装就装”的贪心在“最少段数”问题上永远是最优的证明用交换论证法任何最优方案中从前往后看第一段的右端点都不会超过贪心方案的第一段右端点否则贪心把多出的元素并入后段只会让后段更重归纳下去即可。竞赛里不用写这么细但理解它你才能在面试或笔试被追问时顶得住。5. 常见问题与排查技巧这些错我全都犯过5.1 死循环和答案差一的终极解法二分答案最经典的问题就是死循环。while (L R)循环配上mid (L R) / 2理论上一定收敛但很多人会把更新写成L mid而不是L mid 1这就会在某个区间长度为2的时候陷入死循环。举个例子L6R7mid6。如果check(6)返回true你执行LmidL还是6区间永远不变死循环。所以对于“找最小值可行点”的二分当check返回true时你要让右边界往左缩Rmid当check返回false时你要让左边界越过midLmid1。另一个常见差一错误是把答案输出成R而不是L或者输出成mid。其实在while结束后L和R是相等的输出哪个都一样。如果你写成mid是在循环里输出的那可能不是最终答案因为最后一次可行mid并不是最小可行值。很多人查了半天最后发现输出写错了位置真的很冤。5.2 样例过了但WA大概率是边界初始值写错了我见过一个很典型的错误写法把L初始化为0R初始化为一个很大的数比如“0x3f3f3f3f”。这样不是不行但如果你在check里没有写“a[i]limit就返回false”那么当中值小于数组最大值时check会把那个超大元素单独成段导致cnt很大最终check可能假性返回false也可能因为cnt初始化问题返回true。总之各种诡异结果都会出现。所以我强烈建议把L直接取成max(a[i])R取成sum(a[i])让搜索区间从严格合法的最小区间开始既省时间又减少边界bug。还有一次某同学写check时用的是“当前段和 limit 才切段”导致每次切段后没有把当前元素计入新段。比如limit10扫描到42410下一个5来了sum510他cntsum0然后下一轮sum55后面1加起来最终漏掉了元素5开新段时的和本身。结果段数统计正确性就有问题。记住切段的同时当前元素必须成为新段的第一个元素所以切段后sum a[i]而不是sum 0。5.3 从超时角度排查你的二分会做几次check每次二分循环做一次O(n)的checklog₂(10^5)大约是17次整体复杂度O(n log sum)在正常OJ上跑1秒完全没问题。但如果你把check写成每次重新计算前缀和或者用了vector之类的东西常数稍大也还好。真正会超时的原因多半是你把二分搜索范围写成了 [0, 10^9] 甚至更大然后check里还嵌套了循环复杂度变成O(n log C)就有点悬了。正常题解里不会超时如果超时先检查是不是用了cin没关同步或者数组开小了导致访问越界。5.4 实战排查速查表症状可能原因解决方案死循环更新语句写成Lmid改成Lmid1输出答案比标准答案小1输出的是mid而非最终L/R输出while循环结束后的L答案比标准答案大1二分边界右端点取小了确保Rsum(a[i])而不是sum-1样例过、大样例错int溢出所有求和变量改long long段数永远偏少cnt初始化为0cnt初始化为1单元素大于limit时误判check缺少防御在check里判断a[i]limit直接false这张表是我反复调试这类题目后总结出来的可以说基本覆盖了所有新手会踩的坑。你如果遇到莫名其妙的问题先照着这张表挨个对照大概率能直接定位。6. 从1436延展开这一模型还能打哪些题6.1 题目变体一分书问题有一类经典题叫“抄书问题”或“分书问题”给你一个数组代表每本书的页数要求分成M组每组连续求“抄得最多的人最少抄多少页”。这就是一模一样的模型连贪心check都不用改改改输出格式就能AC。这类题在比赛中经常出现目的就是检验你是否真的理解二分答案而不是背模板。6.2 题目变体二运货/装载问题还有一类“把货物按顺序装上车每辆车容量为X问最少需要几辆车”。这个就是check函数里把“段”换成“车”把“每段和”换成“每车总重”本质完全一样。如果题目要求输出方案那就需要在check通过后再贪心地从前往后划分并记录每段边界这又是另一个进阶考察点。6.3 题目变体三最小化最大值与最大化最小值的对应如果你把题目改成“每段和的最小值最大化”也就是分成M段后让最短的那一段尽量长那就是另一类题型二分的方向会反过来check从前往后扫改成从后往前扫或者改判断条件。很多初学者分不清这两类建议拿1436作为基准把“最小值最大化”的相关题目比如洛谷P1083、P1525这类并查集二分的题拿来对照着做感受二分答案在不同约束方向上的写法差异。我自己刷题的习惯是每做一道二分答案题就把它归入“最大值最小化”或“最小值最大化”两大类并写清楚check函数里那个贪心到底是要“尽量多装”还是“尽量少装”。这个分类一旦建立以后遇到看似陌生的题第一眼就能识别出二分答案的指纹。7. 这道题给我的三点实在启发第一点写二分答案的题先写check再写主循环。我见过太多人一上来就写while、mid写到一半才想起check函数没写明白结果整个逻辑乱成一团。我的顺序永远是先在纸上把“给定一个X怎么判断”搞清楚再动键写代码。check函数是这道题的灵魂主循环只是套壳。第二点边界问题不是靠背口诀解决的是靠手算小样例解决的。每次调二分我都会拿一组形如n5、m3的小数据把L、R、mid、check结果手算一遍确保每一步都符合预期。这一步虽然费时间但比在代码里瞎打printf快得多。第三点多做变体题才能把模板内化成直觉。1436本身不难但如果你只做这一道下次遇到“输出每段具体内容”的变体还会懵。我一般建议把1436、分书问题、运货问题三连做再自己改造题目比如把数组改成负数也能处理吗不能因为只要数组里有负数就不能用贪心从左到右分段了那必须上DP。这个认知会让你对模型的适用范围有更清晰的感觉而不是拿着锤子看什么都是钉子。最后再说一个非常实际的小技巧如果你在赛场上实在忘了边界怎么写可以从L0、Rsum开始然后加一个特判“如果a[i]mid直接return false”这样即使L取小了也不会误判最多是多几次二分。稳定大于炫技这是我在无数场比赛里用血泪换来的经验。