1. 先把题目还原这不是字符串题是个数组切分模型1.1 题目大意当时点开这场练习赛的 G 题看到题目名字叫《分割》我心里第一反应是可能要处理字符串或者是什么后缀数组、回文划分之类的题目。读完题才发现完全不是那么回事。题面给了一个长度为 n 的非负整数数组 a要求把它切成连续的 m 段每一段都不能为空然后定义这种切法下最大的那段的和为整个方案的代价问所有切法中这个代价最小是多少。数据范围 n 和 m 都到了 10^5 级别数组元素在 0 到 10^9 之间。这个数据范围一出来什么暴力枚举切法、直接区间 DP 全部判了死刑。我们需要的是一个和 n 几乎线性、或者至多带一个 log 的算法。题目的描述本身不复杂但连续切 m 段和最大段和最小化这两个词放在一起很容易让人往动态规划方向想尤其是刚刷完区间 DP 题单的人第一眼绝对会写出 dp[i][j] 表示前 i 个数分 j 段那样的转移。这题有意思的地方在于它考的不是你 DP 优化练得多熟练而是你能不能从恰好 m 段这个约束里跳出来看到二分答案加贪心检验这条路。下面我会把从暴力思路到正解的完整推理过程写出来这个过程比 AC 本身更有价值尤其是恰好 m 段到底应该怎么处理我比赛时在这里踩了整整二十分钟的坑。1.2 第一版思路区间DP与它的复杂度死穴如果按最朴素的想法设 dp[i][k] 表示把前 i 个元素分成 k 段时最大的那一段和的最小值那么转移可以写成dp[i][k] min over j i of max(dp[j][k-1], sum(a[j1..i]))其中 sum 可以用前缀和 O(1) 求。这个式子看起来没什么问题逐段枚举切点 j比较前 j 个元素分成 k-1 段的最优值和当前段的和取较大者再取最小。但它的复杂度是 O(n^2 * m)。n10^5 时连一次 O(n^2) 都撑不住更别说再乘一个 m 了。就算用四边形不等式之类的区间 DP 优化在这个数据范围下也不是正解应该有的样子。这个式子还有一个隐蔽问题它把最小化最大值作为目标直接塞进了状态里导致状态必须同时记录分了几段和末尾位置两层信息缺一不可很难压缩。即便把其中一个维度用二分替代也只是从 O(n^2m) 变成 O(n^2 log S)核心的 O(n^2) 依然卡死。所以看到这种数据规模第一件事就是放弃逐段枚举的 DP 念头去找更有整体性的判定方法。对比维度暴力区间DP二分答案 贪心状态数量O(nm)无状态只有阈值 x单次转移复杂度O(n)O(n) 一次扫描总复杂度O(n^2 m)O(n log S)代码难度中低适合的数据范围n 500 左右n, m 1e5 甚至更大1.3 为什么闻到二分答案的味道当问题出现最大值最小或者最小值最大时八成的题都在暗示二分答案。原因是这种目标天然具有单调性如果代价 X 可行那么任何比 X 更大的代价也一定可行因为你只需要沿用原来的切法所有段的和依然不会超过这个更大的阈值。反过来如果 X 不可行比 X 更小的阈值也不可能突然变得可行。这个单调性让求最小可行代价变成了二分 X然后反复回答 X 是否可行。而二分答案的复杂度瓶颈往往就在于这个是否可行的判断只要判断函数能做到 O(n) 扫一遍整体 O(n log S) 在 1e5 量级下就非常舒服。这题判断过程比很多人想的还要简单固定 X 之后我们从左往右扫数组能不放就尽量不放新段一直累积到再加一个元素就会超过 X的时候才被迫切一刀最后统计总共切了几段。这个贪心策略就是经典的书本抄写问题的判定思路。但真正让这题区分度拉满的是接下来段数和恰好 m 段之间的换算关系这也是我在现场卡住的地方。2. 恰好m段和至多m段之间藏着本题最关键的跳板2.1 判定函数到底该判什么固定 X 后的贪心会得到一个段数 cnt这个 cnt 是在每一段和都不超过 X 的前提下最少需要切几段。很多人做到这里会直接写 return cnt m然后挂在样例或者某个大数据上。正确的条件其实是 cnt m。原因在于我们求解的是恰好切成 m 段但二分检验的是是否存在某种不超过 X 的合法切法。如果最少 cnt 段能做到说明存在一个方案只用了 cnt 段当 cnt m 时我们可以从这段方案里挑一段较长的段在中间切一刀把它变成两段。因为数组元素都是非负整数切完之后每一段的和都不会超过原来那一段的和也就仍然不会超过 X。于是原来的合法方案在切了一刀之后依然合法段数却增加了 1。重复这个过程就能从 cnt 段一路加码到正好 m 段。但这个加刀操作有一个前提总段数最多只能是 n因为每一段至少包含一个元素。题目给定了 m n而 cnt 1所以只要 cnt m n就一定可以通过不断拆段从 cnt 凑到 m。这就是为什么判定条件写成 cnt m 而不是 cnt m。我当时写成了等于结果二分出来的答案永远比正确答案大样例还偏偏能过因为样例里贪心段数刚好等于 m这种假象最害人。2.2 非负整数为什么能放心贪心这个拆段合法的论证依赖一个非常关键的性质所有元素非负。假如数组里有负数拆段后某一段的和可能反而变大原来不超过 X 的段拆开了未必继续不超过 X整个贪心就崩了。这也是不少类似题会在题面里专门强调非负整数的原因它不是随便给的约束而是整个算法成立的地基。顺着这个性质还能解释贪心为什么是最优的当我们从左往右扫只要当前段还能容纳下一个元素就继续塞说明我们没有提前切出多余的段得到的 cnt 就是最少段数。任何其他合法方案要么段数相同要么因为切得更早而段数更多不可能比贪心得到更少的段数。所以最少段数 cnt 能被一次性算出来这也是为何这题不需要再套一层 DP 来求最少段数。如果题目去掉非负条件这个贪心就需要重新设计可能要改成每段和不超过 X 的最少段数用 DP 去求复杂度会肉眼可见地上升。所以很多时候数据范围里的每一个约束都不是白给的非负整数这个看似不起眼的设定实际上决定了正解是 O(n log S) 还是 O(n log S log A) 甚至更复杂。2.3 二分边界与单调性细节二分下界不一定要从 0 开始。更聪明的做法是取数组的最大值 L max(a[i])因为任何一段只要包含这个最大值段和就不可能小于它所以答案不可能低于 L。上界直接取整个数组的和 S因为把整段作为一段的时候最大段和就是 S。这样二分范围就是 [L, S]既不会漏答案又能省掉几次判断。如果数据比较大S 可能达到 1e14 量级n 取 1e5每个数取 1e9所以所有和相关的变量都要开 long long。二分时 mid 的单调性是显然的X 越大cnt 只会变小或不变可行性只会从 false 变 true这保证我们可以放心使用 while (L R) 的标准二分。如果你用的还是左闭右开或者整数二分的另一套写法只要保证不变量正确即可别在边界调整时把自己绕晕。提示二分的判断函数只依赖数组和当前阈值 x尽量写成独立函数或 lambda。这样不仅能复用也方便在调试时单独打印某一轮 x 的 cnt 结果快速定位逻辑错误。3. 完整代码与实战踩坑记录3.1 一份能直接上手的C实现#include bits/stdc.h using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorll a(n); ll sum 0, mx 0; for (int i 0; i n; i) { cin a[i]; sum a[i]; mx max(mx, a[i]); } auto check [](ll x) { ll cur 0; int cnt 1; for (int i 0; i n; i) { if (a[i] x) return false; if (cur a[i] x) { cnt; cur a[i]; } else { cur a[i]; } } return cnt m; }; ll L mx, R sum; while (L R) { ll mid (L R) 1; if (check(mid)) R mid; else L mid 1; } cout L \n; return 0; }代码不长核心就两个部分check 函数里的贪心扫描以及主函数里的整数二分。check 函数中 cnt 的初值我这里写的 1含义是整段至少要先算一段然后每强制切一刀 cnt 就加 1。如果写成 cnt 初值为 0需要在循环结束后判断 cur 0 再 cnt两种写法等价但不要混着用否则会出现段数多一或少一的偏差。3.2 我踩的第一个坑long long第一版我不小心把数组开成了 int前缀和处理也用 int。前几个样例数据小全部通过一到大数据就莫名其妙出乱码一样的答案。后来检查才发现n1e5、a[i]1e9 时总和是 1e14int 根本存不下溢出的结果会让二分上界变成负数check 函数自然整个失效。这类范围和值域明显达到 1e14 的问题应该在写代码之前就把所有参与加法运算的变量统一成 long long而不是等 WA 了才回头改。这里还有一个容易忽略的点即使数组本身的答案不会超过 int 范围二分过程中的上界 R 也可能因为 sum 溢出而变成一个很小的数导致整个二分区间错误。所以不要抱着最后答案应该不大的侥幸心理和值相关的变量必须用 64 位整数一次到位。在 C 里就是 long long在其它语言里注意对应类型。3.3 第二个坑a[i] X 的分支二分的 mid 不一定总是大于等于数组中的最大值。比如下界取的 max(a[i])理论上 L 不会小于最大值mid 也会始终不小于 L所以 a[i] x 的提前终止大概率不会触发。但严谨起见check 里还是要保留这个判断尤其是如果哪次写二分把 L 初始成了 0这个分支就会救你命。我实际测过没有这个分支时绝大多数数据也不会炸因为贪心扫描遇到 cur a[i] x 会直接切段把 a[i] 单独作为一段 cur 会被赋成 a[i]如果 a[i] xcur 仍然大于 x下一轮继续切cnt 会异常变多最终 cnt m答案被错误拉高。加了判断就能提前返回 false保证正确性。属于写的时候觉得很啰嗦、实际上很有用的防守代码。3.4 复杂度与极端数据表现整份代码的时间是 O(n log S)S 是元素总和。哪怕 S 到 1e14log2(1e14) 大约 47也就是最多跑 47 次 check每次 check 是 O(n) 的一次遍历1e5 的 n 跑完大约在几百万次操作级别任何评测环境下都毫无压力。空间上只有一个数组和几个变量O(n) 都算不上负担。如果是多组测试数据注意每组数据都要把 sum 和 mx 重置或者直接在循环里重新算别复用上一组的全局变量。我用的是 lambda 捕获引用每次都重新生成所以没踩到重置坑但如果用全局数组就要格外小心。这个实现思路在内存和时间上都留了很大的富余量可以说是一个比较稳的模板。4. 不用二分也能做DP路线以及两个常考变形4.1 O(n²m)的分段DP以及它为什么过不了前面提到 dp[i][k] min over j i of max(dp[j][k-1], sum(j1, i))。这个 DP 在 n 和 m 都小的时候可以用比如 n 500m 500O(n^2 * m) 也就是 1.25e8 级别优化一下也许能跑。但一旦 n,m 到 1e5这个状态数本身就已经是天文数字根本不可能枚举。如果硬要救这个 DP可以固定 X 之后做最少段数DPf[i] 表示前 i 个数在每段和不超过 X 时的最少段数f[i] min(f[k] 1)其中 k 满足 sum(k1,i) X。用双指针维护最小的可行 k再用单调队列维护区间 min可以把 check 降到 O(n)然后外面再套二分。这算是对二分 贪心的一种 DP 化理解也能解释为什么二分答案在这题里几乎是唯一稳妥的路线。从这道题的经验来看遇到分段最优问题先花两分钟估算一下 DP 状态数和转移复杂度如果明显超界就该立刻转到阈值判定的思路上来。很多时候最优解的代码反而比暴力 DP 更短因为时间开销被二分和贪心分摊掉了。4.2 最大化最小值题型的共性识别这次 G 题其实是最小化最大值家族里最经典的一种。这类题的识别信号有三个第一目标函数是 max 或 min 套在某个分段上第二数组或序列存在连续切分的操作第三单次判断某个阈值是否可行可以设计成 O(n) 扫描。三个条件同时满足二分答案的概率就非常高了。反向也很有用如果题目把目标改成每段和的平方和最小这样带累加结构的目标二分答案就不太合适因为判定阈值变得不单调这种题往往需要用斜率优化 DP 或者 wqs 二分。判别标准不是长得很像而是阈值可行性是否具备单调性。赛场上能快速识别出这些套路往往比会背模板更重要。4.3 另一个常见变形每段异或和等于和的分割赛后我又想到一个延伸模型给定非负数组要把它分割成若干段使得每一段内所有数的异或和等于它们的和求最多能分成几段。这个条件看起来是另一个分割问题但它和最值二分关系不大核心是位运算性质a xor b a b 当且仅当 a b 0即两个数没有任何一位同时为 1。扩展到一段内多个数异或和等于和等价于这一段内任意两个数在同一二进制位上不同时为 1。于是解法变成维护一个二进制占用集合从左往右扫如果新数字与当前集合按位与为 0就加入集合否则被迫开新段并把集合清空再从当前数字开始。这个过程同样是 O(n log A) 的。它和分割题放在一起说明这类题真正考的不是某一个数据结构而是你能不能把段的约束翻译成可贪心的条件。多见识几个变形下次遇到类似题面就不会被唬住。5. 复盘下次再见到分割我会按这个顺序思考5.1 一整套思考链经过这题我给自己总结了一套固定的思考顺序写出来供参考。第一步确认分段是连续切分还是可以乱序分组这决定了模型是序列 DP 还是背包/网络流。第二步看目标是否是 min(max(...)) 或 max(min(...))是则优先怀疑二分答案。第三步思考一个固定阈值 X 下能否用贪心或简单 DP 判断可行并分析是否有至少/至多段数的转化空间。第四步写 check 之前把单调性、上下界、整数溢出三个点先想清楚再动键盘。这套顺序在这题里几乎完美运转题目是连续分割目标是最大段和最小化阈值下贪心可获得最少段数再通过 cnt m 完成恰好段数的转化。整个过程花的时间远少于我在 cnt m 上面纠结的时间。如果每次遇到未知题都能快速过一遍这套思维链很多看似复杂的题目其实都能归约到自己熟悉的模型上。5.2 易错点清单把这题的坑集中列一下判定条件必须写成 cnt m 而不是 cnt m。所有累和变量用 long long不要把数组和前缀和开成 int。二分下界最好取数组最大值而不是 0能减少二分次数。check 里保留 a[i] x 的提前返回防止阈值过小时段数失控。cnt 初值是 1 还是 0要和循环体保持一致避免段数多算或少算。确认题目约束 m n否则拆段凑数的论证不成立。还有一个非常隐蔽的细节当数组中出现大量 0 时贪心的段数可能非常小此时 cnt m 几乎是必然成立二分会偏向小数方向但答案不会低于 mx所以下界取 mx 仍然安全。零元素不会破坏拆段合法的推理因为拆出的零段和非负元素的论证完全一致。5.3 根据这场题总结的两个小技巧最后分享两个小技巧。第一个二分答案的 check 函数尽量写成独立 lambda 或函数里面只依赖数组和当前 x方便多组数据复用也方便在主函数里打印某些中间值来调试。第二个如果遇到需要恰好分成 k 段而要判断最少段数是否不超过 k的情况可以在草稿纸上把从 cnt 拆到 m的一刀一刀画出来确认每刀切完后段和不会变大只有这一步想通了代码里的不等号才敢放心写。这题本身不难但把最小化最大值恰好段数非负整数几个点串在一起之后含金量就上来了。如果我在赛前能把这类模型的思考链过一遍G 题应该能省下不少时间。希望这篇复盘也能让看的人少踩一次 cnt m 的坑。