我是在一个在线题库里翻到这道题的，编号排到 G，题名却只有两个字：分割。第一眼看上去，标准的区间 dp 脸，数据范围给得又不小，差点就把我做自闭了。可等我真正把题读进去才发现，这个题其实连 dp 数组都不需要，核心就是一层等价转换：把“切 k 段”想成“删掉 k-1 条缝”。想通这一点，代码短到让人怀疑是不是骗样例，复杂度也就是一次排序的事。

因为原题面描述比较精简，以下我按“分割”类题目最常见的完整设定展开：给定 n 个整数，你可以先任意重排这些数，再把它切分成 k 个非空连续段，每段成本是段内最大值减最小值，目标是让 k 段成本总和最小。这个版本最能体现题目背后的算法思想，也是我实际刷题时最常遇到的一种变体。如果你拿到的题明确要求不能重排、只能按下标连续切，那请看第 4 节，那完全是另一套做法。

1. 拿到“分割”这个题名，先别急着写代码

1.1 先把题面翻译成人话

原题没有给我多余的解释，所以我先把可复现的完整设定写清楚：

注意第一行的“可先任意重排”。这四个字决定了整个题目的方向。重排之后，段内最大值、最小值只取决于你选了哪些元素，谁在左边谁在右边完全不影响成本，所以这个题本质上是“把一堆数分成 k 组，让组内极差之和最小”，而不是“在保持原序的数组上切几个口子”。

我在写暴力版本之前，先把这两种情况分开，就是因为实际踩过坑：有的“分割”题允许重排，有的不允许，两者做法天差地别。你如果第一眼没确认这个条件，后面代码写得再花哨都是白搭。

1.2 我最初冒出来的暴力想法

第一反应当然是动态规划。设 dp[i][j] 表示前 i 个数分成 j 段的最小总成本，转移就是枚举上一段结束的位置 t：

dp[i][j] = min(dp[t][j-1] + cost(t+1, i))

其中 cost(l, r) 是区间 [l, r] 内最大值减最小值。如果 n 是 200，这个做法完全没问题，预处理一下区间最大最小值，三层循环跑完收工。但这个题 n 能给到 1e5 量级，k 又能取到 n，那复杂度就是 O(n²k)，别说是本地跑，我样例都不太敢造大的。

有经验的人会想到四边形不等式优化，但那东西在“极差”这个区间函数上不一定满足单调性要求，盲目上决策单调性优化是给自己挖坑。更关键的是，即便优化到 O(nk)，面对 n=k=1e5 这种输入，依然超时。所以这个题一定存在面向数据范围的结构性结论，不需要枚举分界点。

1.3 突破点：段成本是“极差”，不是“和”

我后来盯着段成本的定义看了很久，发现一个很容易被忽略的事实：段内最大值减最小值，本质上就是这个段在数轴上覆盖的“长度”。如果一组元素全部落在 5 到 9 之间，那不管排列顺序怎么变，这组的成本都固定是 9 减 5。

这给我的启示是：别把每个段看成区间，要把所有元素看成数轴上的点。切分就是在数轴上选几个位置把它们隔开。既然允许重排，那我完全可以把所有点先排成一条有序链，再考虑从哪里断开。排序之后，很多问题会变得非常具体。

2. 破题核心：把“切 k 段”换成“删掉 k-1 条缝”

2.1 排序之后长什么样

假设输入是 [4, 1, 8, 5, 2, 7]，先排序得到：

[1, 2, 4, 5, 7, 8]

相邻元素之间的差值：

1, 2, 1, 2, 1

整个数组的跨度是 8 - 1 = 7。如果 k=1，也就是不切，一整段的成本就是 7。现在 k=3，我们需要在这个有序序列里切两刀。

切在哪个位置，等价于在两条相邻元素之间的“缝”上动刀。比如我切在 1|2 和 4|5 这两条缝，得到三组：

[1] [2,4,5] [7,8]

[1] 的成本是 0；[2,4,5] 的成本是 5-2=3；[7,8] 的成本是 1，总成本就是 0+3+1=4。

这时候你会发现，总成本其实就是没被切掉的那些“缝”的数值之和。被切掉的两条缝，它们的数值反而从总跨度里被剔除了。

2.2 从样例里找出规律

我们重新看排序后的数组和相邻差值：

总跨度为 7。如果 k=3，要切两刀，那两刀尽量切在最贵的两条缝上，也就是两个“2”。把两条值为 2 的缝切掉之后，剩下的缝值加起来正好是 1+1+1=3。

对应的切法是：

[1, 2] [4, 5] [7, 8]

三段成本分别是 1、1、1，总和正是 3。

这不是巧合。任何一组 L 到 R，成本就等于它内部所有缝的值求和。全部元素放在同一段时，总成本是全部缝值的总和。每切开一条缝，就该段总成本中去掉这条缝的贡献。因此，总成本 = 总跨度 - 被切开的所有缝值之和。要最小化总成本，就要最大化被切开的缝值之和，也就是选 k-1 条最大的缝切开。

2.3 严谨证明一下贪心正确性

排序后得到 b[0] ≤ b[1] ≤ ... ≤ b[n-1]，相邻缝定义为:

g[i] = b[i+1] - b[i]

任意一组 [L, R] 的成本为：

b[R] - b[L] = g[L] + g[L+1] + ... + g[R-1]

所以 k 组的总成本等于所有被某组覆盖的缝值之和。切开位置会割断相邻两个组的边界，那一条缝不再被任何组覆盖。总共有 k-1 个切口，所以总成本等于：

所有缝之和 - 被切开的那 k-1 条缝之和

第一项是常数，第二项越大总成本越小。要让第二项最大，就直接取最大的 k-1 条缝。贪心成立，不需要任何 dp。

2.4 边界情况必须单独确认

k=1 和 k≥n 这两个分支在代码里一定要写清楚，否则缝隙数组可能为空，或者出现 k-1 超过缝隙数量的情况。我第一次写的时候没处理 k≥n，结果在随机数据上直接数组越界，教训深刻。

3. 完整 C++ 实现，可以直接抄作业

3.1 代码本身非常短

思路一旦清晰，代码就是排序加排序。写成 17 行足够，我最终提交的版本长这样：

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin >> n >> k; vector<long long> a(n); for (int i = 0; i < n; ++i) cin >> a[i]; sort(a.begin(), a.end()); long long total = a.back() - a.front(); if (k == 1) { cout << total << '\n'; return 0; } if (k >= n) { cout << 0 << '\n'; return 0; } vector<long long> gaps; gaps.reserve(n - 1); for (int i = 0; i + 1 < n; ++i) { gaps.push_back(a[i + 1] - a[i]); } sort(gaps.rbegin(), gaps.rend()); long long removed = 0; for (int i = 0; i < k - 1; ++i) { removed += gaps[i]; } cout << total - removed << '\n'; return 0; }

这里我先把原数组排序，算出总跨度；再把每条缝排序，从大到小取前 k-1 条求和。最后用总跨度减掉这些缝值，就是答案。

3.2 为什么我用两个 sort 而不是 nth_element

有人会问，k-1 条最大的缝，只求部分排序不是更快吗？确实可以，比如用nth_element找到第 k-1 大的缝，再扫一遍求和。但这里有两个问题：

第一是并列元素。如果第 k-1 大的缝值有多个，单纯找分界点之后，你还需要统计有多少个等于该值的缝需要计入，边界处理容易写错。

第二是这个题的 n 通常到 1e5 到 2e5 量级，两次sort一共 O(n log n)，实测也就几十毫秒，根本没有优化到nth_element的必要。宁可代码可读性高一点，也不要为了微小的常数优化引入各种 off-by-one。

提示：如果你想炫技，可以只对 gaps 做一次partial_sort，取前 k-1 个最大的缝。但请务必在本地先跑一跑并列数据的测试。

3.3 大数问题必须用 long long

元素绝对值最大 1e9，n 最大 2e5，总成本理论上限是 2e14 量级。这个数已经远超 32 位整数的范围。我用long long装数组和最终结果，避免溢出。

还有一种隐蔽溢出发生在“总跨度”这一步。如果数组里有 -1e9 和 1e9，排序后a.back() - a.front()得到 2e9，这个数值恰好能塞进 int，但用它去减若干条缝值就可能变成负数之外的不确定值。稳妥起见，从一开始就用long long。

4. 如果题目不允许重排，解法完全不同

4.1 两种“分割”题怎么区分

同样是“分割”，不同题可能完全是两个物种。区分方法很简单：看题目里有没有“连续子数组”“保持原顺序”“只能按下标顺序切”这类描述。如果有，那不能排序；如果允许分组、允许重排、只关心集合，那才能走第 3 节的路。

举一个很直观的例子，数组 [5, 1, 9, 3]，k=2。

如果允许重排，最优分组是把 [1,3] 放一组、[5,9] 放一组，成本是 (3-1)+(9-5)=6。如果不允许重排只能按原顺序切，最优是 [5,1] 和 [9,3]，成本是 (5-1)+(9-3)=10。

两个答案差这么多，你要是拿排序解法去做“连续子段版”，样例可能过，隐藏数据必挂。

4.2 连续子段版本的核心 dp

如果题目真的要求保持下标顺序，那第 2 节的结论必须全部放弃，回到区间 dp 思路上来。转移公式是：

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

其中 t 从 j-1 枚举到 i-1。为了快速获得任意区间 [l, r] 的最大值和最小值，可以提前建立稀疏表，把预处理做到 O(n log n)，查询做到 O(1)。dp 整体复杂度是 O(n²k)，所以这种版本通常只会在 n 比较小的时候出现，或者配合其他技巧使用。

不要把两个版本混着写。我在本地对比过，排序版代码跑在“连续版”数据上，经常输出一个偏小的数，因为自由重排天然能消掉段内大极差，而顺序约束会把大极差锁在段里，成本必然更高。

4.3 怎么做到一看题就知道题型

我现在的习惯是拿笔把题面里的关键词圈出来：

• 出现“连续”“子数组”“原顺序”，默认走区间 dp 路线；
• 出现“任意排列”“分成 k 组”“无关顺序”，优先往排序和贪心想；
• 如果两种可能都有，那必须从样例反推，或者直接用小暴力试跑一遍再确认。

这比硬背算法模板可靠得多，因为竞赛题最喜欢在“看起来差不多的名字”里藏完全不同的约束。

5. 我踩过的坑与排错实录

5.1 把“切 k 段”写成“切 k 刀”

第一版代码里我把循环写成了：

for (int i = 0; i < k; ++i) removed += gaps[i];

k=3 时切了 3 条缝，等于分成了 4 段。答案自然偏小，甚至会输出 0。这个错误本质上是没有理解“段数”和“刀数”的关系：切 k 段只需要 k-1 刀。修好后我特意在本地加了一组测试：

输入： 6 3 4 1 8 5 2 7

正确输出应该是 3，错误版本会输出 1。如果你也遇到答案比预期小的情况，先检查是不是多切了一刀。

5.2 n=1 时脚本直接跪了

我当时拿到手的第一版在 sort 之后立刻求 a.back()-a.front()，然后开始枚举缝隙。当 n=1 时，a.back()-a.front()等于 0，本来没问题，但如果后面没有提前退出，执行到 gaps 循环时就会出现对空数组的越界访问。

后来我在代码里加了两道防线：k==1 时直接输出总跨度，k>=n 时直接输出 0。这样 n=1 的情况无论 k 是多少都不会走到缝隙数组相关逻辑。

5.3 多组数据测试时没重置状态

很多题库喜欢一直读到 EOF。我的测试脚本一开始用单组数据验证，没问题后改成多组循环，结果发现上一次排序留下的数据被带进了下一组。

后来统一改成在循环内部定义vector<long long> a(n)和gaps，让它们每次重新构造，状态自然清空。代码短的情况下强烈建议用这种局部变量方式，不要定义一个全局 vector 再手动 clear。

排查技巧：如果多组数据下偶尔出现奇怪大数，优先怀疑是不是没有清空容器，而不是去查算法本身。

5.4 读题时以为“分割”就必须按原顺序

这是我自己最痛的教训。我一开始把题理解成连续切分，想了很久的单调队列优化 dp，越写越复杂。后来重新读题面，发现条件是“任意排列后再分割”，瞬间意识到没必要 dp。

从那以后，拿到这种题我做的第一件事永远是确认“能不能重排”。如果原题描述很含糊，我会直接写一个 n 很小的小暴力，把两种解释都跑一遍，看看哪个和样例对得上。这个习惯帮我避免了好几次在错误模型上浪费半天时间。

6. 这类“分割题”的通用识别方法

6.1 一个很实用的判断公式

凡是段成本是“段内极差”“段内最大最小值之差”的分割题，都可以先问自己一个问题：如果把段内元素洗牌，成本会变吗？

• 不会变，那考虑排序、贪心、数轴缝隙；
• 会变，那要考虑顺序相关 dp 或双指针。

这个公式看着简单，实际非常有效。因为很多分割题会把成本定义成“最大值减最小值”，这就是在暗示你顺序不重要。一旦抓住这一点，你就能把一道看似需要复杂数据结构的题，化简成“排序后删掉最大缝隙”的结论。

6.2 我对这类题的答题习惯

最后分享一个我自己的习惯：面对“分割”类题目，我会先手算一组小样例，比如 n=5、k=2，把所有可能切法列出来。这个过程不会浪费太多时间，但能让我把抽象的公式落到具体数字上。

我在实际解题中发现，很多人不是不会排序，而是不敢把“切段”和“删缝”划等号。总觉得切段应该是在维护某段内部的信息，实际上只要你把整段跨度全部摊开成相邻差值，每一刀切在哪条缝上，答案就完全由那条缝的值决定。这种思维转换，比背下任何模板都重要。

这道题也给我一个提醒：压轴题未必需要高大上算法，很多时候考验的是你愿不愿意把问题换一个角度重新描述一遍。搜索完所有已知模板找不到答案时，退回到最原始的定义，往往比继续堆优化更能找到出口。