企业官网建设流程全解析

“分组”这两个字一出现在题目名里，十有八九是在考你有秩序地做决策。今天要写的这道题，我在刷题群里看人问过好几遍：给你一个数组，要求按顺序切成恰好 k 段，让所有段的和里面最大的那个尽可能小。拿到题第一反应可能是动态规划，但这篇题解会告诉你，更适合的解法是二分答案加贪心判定——这也是整个“最小化最大值”题型的地基。

适合谁看？刚开始练二分的同学、准备算法面试的开发者，还适合那些写 check 函数时总差一个等号的倒霉蛋（我承认我也曾是）。不需要复杂的数学，数组非负，思路直观，代码二三十行就能收工。下面从题目拆解开始，把每一步为什么这么走都讲清楚。

1. 先把“分组”翻译成人话

1.1 题意还原与样例

题目长这样：给定一个长度为 n 的非负整数数组 nums，以及一个正整数 k，要求把数组按原有顺序切成恰好 k 段连续子数组，每段非空，然后计算这 k 段各自的和。希望这 k 个和中的最大值尽量小，输出那个最小的“最大段和”。

光看定义有点绕，我们用一组数据走一遍。假设：

nums = [7, 2, 5, 10, 8]
k = 2

可以切成 [7, 2, 5] 和 [10, 8]，两段和分别是 14 和 18，最大值为 18。也可以切成 [7, 2] 和 [5, 10, 8]，两段和是 9 和 23，最大值是 23。还可以切成 [7] 和 [2, 5, 10, 8]，最大值是 25。比较下来，18 就是所有切法里“最大段和”最小的那个，答案输出 18。

这个例子很经典，因为它会出现“单段和很大但另一段很小”的极端情况，逼着你思考怎样把负载摊匀。注意一个关键点：题目说的是“连续子数组”，也就是切完之后段与段之间不能交换元素顺序，更不能把元素挑出来重新组合。这个约束决定了后面整套算法方向。

1.2 连续与非连续的天壤之别

同样是“分组”，连续与不连续是两个物种。

如果允许打乱顺序再分组，那问题就变成类似“把 n 个数装进 k 个袋子，让最重的袋子尽量轻”。那种题往往用贪心加最大堆，每次把当前最大的数塞进当前总和最小的袋子里，思路完全是另一套。但本题要求保持顺序，实际上就是你在原数组上插 k-1 把“剪刀”，剪刀之间不能交叉，切完的每一段保持原样。

这个连续性假设在现实生活中非常常见。你想想生产排程：一批订单必须按照先后顺序在一条流水线上加工，你想把它们分成 k 个批次，每个批次的加工时长不能差太多，这就是连续分组。日志系统按时间顺序落盘，要切成 k 个文件分片，也不可能把后面的日志插到前面去。所以题目不是故意刁难你，它模拟的是很实际的约束：顺序不能乱，负载要均衡。

1.3 为什么暴力切分想都不用想

n 个数，切成 k 段，相当于在 n-1 个空隙里选 k-1 个位置下刀，组合数是 C(n-1, k-1)。当 n=30、k=15 时，这个数已经超过 7700 万；n 到 100 的时候就彻底爆掉了。所以暴力枚举切点这条路，第一秒就可以放弃。

剩下两条路：动态规划，或者二分答案加贪心判定。两条路都能解，但适用场景和复杂度差别很大。动态规划是“正面硬刚”，把状态定义成“前 i 个数分成 j 段的最优值”，思路很直观，但朴素转移是 O(k n^2)，遇到 n=10^5 直接超时。二分答案则是“曲线救国”：不直接找最优切法，而是先猜一个答案 X，再检查“能不能用不超过 k 段让每段和都不超过 X”。这个检查过程是 O(n) 的，而二分只需要 log(总和) 轮，整体 O(n log n) 级别，跑起来舒服得多。

我个人的判断习惯是：看到“最大值最小”或者“最小值最大”这种字眼，先在心里给二分答案记一笔。它大概率不是唯一解，但往往是性价比最高的解。

2. 二分答案 + 贪心：这道题的最短路径

2.1 换一个问法：给你一个上限 X

二分答案的核心思想，是把“求最优值”改成“判可行性”。原问题问的是：最优的最大段和是多少？现在换成：我随便给定一个数 X，你告诉我有多少种切法能保证每一段的和都不超过 X。

举例来说，nums = [7, 2, 5, 10, 8]，k = 2。如果 X = 15，能不能切成至多 2 段，每段和都不超过 15？试试看：第一段从 7 开始，加 2 得 9，再加 5 得 14，再加 10 就成 24 超了，所以第一段只能到 [7, 2, 5]。第二段从 10 开始，加 8 得 18，也超了 15，所以第二段只能是 [10]，第三段 [8]。切出来是 3 段，超过 k=2，说明 X=15 不可行。

如果 X = 18，第一段 [7, 2, 5] 和是 14，没超；第二段 [10, 8] 和是 18，刚好等于 X，两段搞定，可行。所以这个例子中答案在 16 到 18 之间的某个位置。至于为什么最终是 18 不是 17，可以自己拿 17 试一遍，会发现无论如何都要切成 3 段。

这样一来，问题就从“找出最优切法”变成了“判断 X 是否可行”。而“判断”这件事，比“求解”简单太多，因为我们可以用很粗暴的贪心策略。

2.2 单调性：二分合法的底气

二分能工作的前提，是答案具备单调性。这里非常明显：X 越大，每段能装的东西越多，需要切出的段数只会越少；X 越小，段数只会越多。所以“X 可行”这个属性是单调的：一旦 X 可行，那么所有比 X 大的数一定也可行；一旦 X 不可行，所有比 X 小的数一定也不可行。

用一句人话说：可行性函数是一个只有 false 和 true 两段的阶梯，左边全是 false，右边全是 true，我们要找的是 true 区域最左边那个点。这就是二分的标准适用场景。

上界和下界也好定。下界不能比数组里最大的单个元素小，因为无论怎么切，那个最大的元素自己所在的那一段，和至少等于它本身。所以下界 L = max(nums)。上界可以是 sum(nums)，因为当 X 等于总和时，不分段就是一段，段和等于总和，一定可行。这样搜索区间 [L, R] 就是 [max(nums), sum(nums)]，宽度非常合理，不会做无用功。

2.3 check 函数里的贪心为什么敢这么写

判断 X 是否可行的 check 函数，写法极其简单：从左往右扫描数组，累加当前段的和，如果加上下一个元素会超过 X，就在这里切一刀，新段从下一个元素开始。

这个贪心的核心逻辑是：每一段尽量装到不能再装为止。为什么这种“撑满”策略是对的？因为它能保证切出来的段数是最少的。

想一个反证：假设存在一种更优的切法，总段数比贪心切出来的还少。既然贪心每一段都撑到了极限，那么任何其他切法必然存在某个位置，贪心把元素装进了前一段，而更优切法却在这里提前下刀了。提前下刀意味着前一段少装了一些元素，而后一段多装了一些。如果把那个元素从后一段挪回前一段，前一段的和依然不超过 X（因为贪心当初就允许它装进来），后一段的和变小了，当然也不超过 X。于是我们得到一个段数相同甚至更少的新切法。反复执行这个调整，最终可以变成贪心切法，说明贪心切法的段数不会比任何切法多。

用人话说就是：你都把每段塞到最满了，不可能还有办法切出更少的段数。所以 check 函数只需统计贪心切法用了多少段，如果段数不超过 k，说明 X 可行；否则不可行。

这里有个细节值得强调：题目要求“恰好 k 段”，而 check 判断的是“不超过 k 段”。两者等价吗？等价的，前提是 k <= n 且每段非空。因为如果你用少于 k 段就满足了每段和不超过 X，只需要把其中某一段再拆开，拆出来的两段和等于原段和，依然不超过 X，段数就增加了，可以一直加到恰好 k 段。所以“至多 k 段可行”与“恰好 k 段可行”在这个题设下是一回事。很多教程不点破这一点，导致有人写 check 时对段数到底用 <= 还是 == 纠结老半天。

3. 代码怎么落地才不容易写崩

3.1 C++ 参考实现

思路理清了，代码其实很短。先看 C++ 版本，我带着注释写一遍：

#include <bits/stdc++.h> using namespace std; typedef long long ll; // 判断在每段和不超过 limit 的前提下，能否用不超过 k 段分完 bool check(const vector<int>& nums, int k, ll limit) { ll cur = 0; // 当前这一段已经累加的和 int cnt = 1; // 当前已经用了多少段，先默认有第一段 for (int x : nums) { if (x > limit) return false; // 单个元素就超限，谁来了都不行 if (cur + x > limit) { cnt++; // 当前段加不下 x，必须开新段 cur = x; // 新段从 x 开始 if (cnt > k) return false; // 段数超了，提前退出 } else { cur += x; } } return cnt <= k; } int splitArray(vector<int>& nums, int k) { ll left = 0, right = 0; for (int x : nums) { right += x; if (x > left) left = x; // left 至少是最大单元素 } if (k > nums.size()) return -1; // 不可能切成超过元素个数的非空段 while (left < right) { ll mid = left + (right - left) / 2; if (check(nums, k, mid)) { right = mid; // mid 可行，答案不会比 mid 更大 } else { left = mid + 1; // mid 不可行，答案一定比 mid 大 } } return left; }

几个细节我特别说一下。

cnt初始化为 1 而不是 0，是因为扫描第一个元素时还没有“开新段”的动作，但已经在第一段里了。如果你把cnt初始化成 0，后面计数逻辑就得在每个元素处都判断是否开段，容易乱。

left初始化为max(nums)而不是 0，能直接砍掉一段无效二分区间。因为答案不可能小于最大元素，从最大元素开始找是安全的。

mid用left + (right - left) / 2而不是(left + right) / 2，防止两个大数相加溢出。虽然这里 left 和 right 都是 long long，没那么容易爆，但养成这个习惯没坏处。

3.2 Python 参考实现

Python 写起来更短，思路完全一样：

def check(nums, k, limit): cnt = 1 cur = 0 for x in nums: if x > limit: return False if cur + x > limit: cnt += 1 cur = x if cnt > k: return False else: cur += x return cnt <= k def split_array(nums, k): left, right = max(nums), sum(nums) while left < right: mid = (left + right) // 2 if check(nums, k, mid): right = mid else: left = mid + 1 return left

Python 的整型不会溢出，所以 mid 直接写(left + right) // 2也没问题。只不过 Python 在 n 特别大的时候，遍历本身的常数比较大，如果卡性能，可以考虑用 PyPy 跑。竞赛场合用 Python 写这种题基本没压力，因为 O(n log sum) 的复杂度不高。

3.3 边界、溢出和初始化细节

这道题最容易翻车的不是算法，而是边界。

第一，数据类型。题目只给非负整数，但数组长度可能到 10^5，单个元素可能到 10^9，总和能到 10^14 这个量级。用 int 存 sum 和 limit 必炸，C++ 一定要开 long long。别觉得样例能过就万事大吉，样例数据通常温和得骗人。

第二，k 和 n 的关系。如果 k > n，不可能切出恰好 k 个非空段，直接输出 -1 或者按题目要求处理。有些题目没给这种非法数据，但你自己心里要有数。遍历的时候，如果 cnt 已经超过 k，提前返回 false，能省一点时间，也避免后续无意义的累加。

第三，空数组。如果 nums 为空，那答案是多少？不同题目定义不一样。大多数分组题默认 n >= 1，但如果你写通用函数，最好在开头加个判断：空数组时按题意，通常返回 0。否则left = max(nums)会直接报错。

第四，check 里x > limit的判断不能省。我见过有人觉得，反正cur + x > limit时 x 也会被单独开段，于是不写这个判断。但会出现一个隐蔽 bug：如果单个 x 已经大于 limit，你会把它放进一个新段，cur 变成 x，这个 cur 本身就已经超限了，后面再遇到别的元素，又会错误地继续比较。更糟的是，如果 k 恰好很大，这个错误状态可能被 cnt <= k 兜住，返回一个错误的 true。所以单个元素超限直接返回 false，是最干净的处理。

4. 调试实录：那些 WA 到怀疑人生的地方

4.1 边界样例对照表

写代码之前，先把边界样例准备好。我刷题习惯用一张小表做自测，每种边界跑一遍，能过滤掉八成低级错误。这道题我常用的测试用例长这样：

用这些数据跑一遍，基本能保证主流程是对的。真正难的往往是后面几种边界组合，比如“k 恰好等于 n”时，答案就是 max(nums)，而二分法也会正确收敛到 max(nums)。

4.2 二分模板千万不能混

二分模板是重灾区。天天有人把left < right、left <= right、right = mid、right = mid - 1混着写，结果不是死循环就是答案偏一位。

我长期用的模板是左闭右闭的“寻找第一个可行值”：

while (left < right) { mid = left + (right - left) / 2; if (check(mid)) right = mid; else left = mid + 1; }

这个模板的逻辑是：每次循环都保证答案在 [left, right] 区间里。如果 mid 可行，说明答案 <= mid，所以把右边界收到 mid；如果 mid 不可行，说明答案 > mid，所以把左边界收到 mid + 1。循环结束时 left 和 right 相等，就是答案。

关键点在于：mid 可行时right = mid，不要写right = mid - 1。因为你不能排除 mid 本身就是答案的情况。一旦写成right = mid - 1，答案就被排除在搜索区间外了，最后必然出错。同理，不可行时left = mid + 1，不要写left = mid，否则当 left 和 right 相邻时会死循环：left=17, right=18, mid=17，check(17) 为 false，left 仍然是 17，永远跳不出去。

还有一个小习惯：如果你用的是mid = (left + right + 1) / 2这种上取整写法，通常是配合“寻找最后一个可行值”用的。不要在同一道题里来回切模板，选一个背熟比背十个半生不熟强得多。

4.3 段数统计的初始化陷阱

再讲一个我实际踩过的坑：cnt 到底是 0 还是 1。如果你把 cnt 初始化为 0，用“遇到超限就 cnt++，然后 cur = x”的逻辑，跑完循环后总段数是 cnt + 1，因为最后一个段在循环结束时没有触发计数。很多人忘了最后这个 +1，导致 check 返回的段数少 1，恰好错的又不多，样例还容易过，非常阴险。

我建议用 cnt = 1 的写法，循环里每开一个新区段才 cnt++，这样循环结束时 cnt 就是真实段数，不需要额外修正。写 check 函数时先搞清楚“当前这一段的归属”，比硬套公式要可靠。

4.4 一个更隐蔽的错误：恰好 k 段与至多 k 段的等价条件

上文说了，当每段非空且 k <= n 时，“至多 k 段可行”等于“恰好 k 段可行”。但如果你把题设改一改，比如要求“每一段至少包含两个元素”，这个等价关系就不成立了。因为有时候你少切几段可以满足和的上限，但把段继续拆开时，可能拆不出“每段至少两个元素”的合法切法。

所以不要把这个等价条件背成铁律，要理解它依赖的前提：段可以无条件继续拆分。竞赛里大多数连续分组题都满足这个前提，所以 check 里用cnt <= k是对的。但面试时如果面试官加一句“每段长度不能超过 3”，你就要重新审视 check 的写法了。

5. 分组题的亲戚们：DP、变体和选型

5.1 动态规划思路对照

二分答案不是唯一解法。如果你看到这道题第一反应是 DP，说明你状态定义的基本功不错。DP 写法是这样的：

设 dp[i][j] 表示把前 i 个元素分成 j 段时，最小的“最大段和”。转移时枚举最后一段的起点 t，那么：

dp[i][j] = min( max(dp[t][j-1], sum(t+1...i)) )

其中 t 的取值范围是 j-1 到 i-1。边界条件是 dp[0][0] = 0，dp[i][0] = 正无穷（除 dp[0][0] 外）。答案就是 dp[n][k]。

这种做法能理解题目的结构，但对 n 和 k 都很大的情况就无能为力了。复杂度是 O(k n^2)，n=5000 基本到头。所以如果题目给了大的 n，DP 只能用来对拍验证二分答案的正确性。我经常写一个暴力 DP 和一个二分答案，随机生成小数据对比输出，确认二分写对了，再删掉 DP 提交。这个“对拍”习惯帮我抓出过好几个边界 bug。

5.2 分组背包？别和这道题搞混

“分组”这个词在算法里还有另一个常见含义：分组背包。分组背包的问题是：给你若干组物品，每组里最多选一个，放进容量有限的背包，求最大价值。它和这道题完全是两码事，唯一的共同点是名字里带“分组”二字。

分组背包的决策维度是“每组选哪个”，不要求物品连续，也不涉及段和均衡。如果你在准备面试时把两个题混在一起复习，会很混乱。我的建议是：看到“连续子数组”“切成 k 段”这种描述，立刻归到数组分段问题；看到“每组选一个”“每组最多取一个”，立刻归到背包 DP。两条路线互不交叉。

5.3 几个常见变体：至多 k 段、求具体方案、非负改负数

这道题的变体非常多，换一个条件，解法就要跟着调整。

第一个变体：把“恰好 k 段”改成“至多 k 段”。这个最简单，check 函数里cnt <= k的语义本来就是“至多”，所以二分的主流程完全不用改，题目可能还会给你一个更宽松的答案范围。

第二个变体：要求输出具体切法而不只是答案。二分答案算出最优 X 之后，可以再跑一遍 check，并在每次切段时记录切点位置。这里要注意，如果要输出的是“恰好 k 段”的方案，而二分过程只能保证“至多 k 段”，你就需要在记录切点时额外处理：如果贪心切出来的段数小于 k，把其中某些段继续拆开补足段数。具体拆哪一段？拆任何一段都行，只要保证每段非空即可。这个补段逻辑容易写乱，我的建议是：先按贪心切，得到少段方案，再按顺序把每个可拆的段从末尾拆开，直到段数达到 k。

第三个变体：数组里有负数。这就要命了。一旦允许负数，“每段尽量撑满”的贪心不再成立，因为多加一个负数可能会让段和变小，从而可能导致更少的段数。此时二分答案加贪心的基础就崩塌了，必须回到 DP。好在竞赛里这种题很少见，面试也基本不会考，但你需要知道这个边界在哪里。

5.4 什么时候无脑二分，什么时候老老实实 DP

我自己的选型标准很简单：

• 数组非负、要求连续分段、目标是最大化或最小化某个段相关值 → 优先想二分答案 + 贪心。
• 数组有负数、段数限制很小、需要求方案数 → 想 DP。
• 题目明确要求输出所有可行方案 → 想搜索或 DP 回溯。

二分答案的最大优势是 O(n log V) 的复杂度对数据范围非常宽容，check 函数又简单到不容易写错。它最大的劣势是只能给出答案值，不能直接给出方案。如果题目既要你求值又要你构造方案，那就先二分求值，再基于这个值重新构造。

6. 一点题外话：优化问题向判定问题的转换

我个人在实际刷题中的体会是，二分答案这层“转换”比任何模板都值钱。你看到的每个“最大值最小”题，本质上都是一个优化问题：在巨大的决策空间里找一个最优值。直接搜决策空间往往爆炸，但如果能把目标值 X 拿在手里，反问一句“给定 X，可行吗”，问题规模就瞬间塌缩成一个简单判定。

这就像找一条路的最窄处。你不知道最窄处到底多窄，但你可以先假设一个宽度 X，然后沿着路走一遍，看能不能不碰到路肩走完全程。能走通就说明真实最窄处不大于 X，走不通就说明大于 X。反复猜，指数级逼近正确答案。

这个思路不只在算法题里有用。我自己做项目排期时也会用：假设一个总工期，反过来检查每个任务能不能塞进这个工期里，不行就放宽，行就收紧。工具不同，思维一模一样。

最后再分享一个小技巧：写分组题时，先把 check 函数单独拿出来测，用几组手工数据验证“X=0 永远 false，X=sum 永远是 true，X=max 有时 false 有时 true”，确认 check 没问题后再开始调二分。很多人一上来就在二分循环里 debug，问题是 check 的 bug 会被二分循环放大，错误信息层层包裹，越查越晕。分层测试，一次只信一个函数，能省下大量时间。