我是在一个在线题库里翻到这道题的编号排到 G题名却只有两个字分割。第一眼看上去标准的区间 dp 脸数据范围给得又不小差点就把我做自闭了。可等我真正把题读进去才发现这个题其实连 dp 数组都不需要核心就是一层等价转换把“切 k 段”想成“删掉 k-1 条缝”。想通这一点代码短到让人怀疑是不是骗样例复杂度也就是一次排序的事。因为原题面描述比较精简以下我按“分割”类题目最常见的完整设定展开给定 n 个整数你可以先任意重排这些数再把它切分成 k 个非空连续段每段成本是段内最大值减最小值目标是让 k 段成本总和最小。这个版本最能体现题目背后的算法思想也是我实际刷题时最常遇到的一种变体。如果你拿到的题明确要求不能重排、只能按下标连续切那请看第 4 节那完全是另一套做法。1. 拿到“分割”这个题名先别急着写代码1.1 先把题面翻译成人话原题没有给我多余的解释所以我先把可复现的完整设定写清楚参数含义典型范围n整数个数1e5 到 2e5k要切成的段数1 ≤ k ≤ na[i]原始整数绝对值 1e9 以内段成本段内最大值与最小值之差非负总成本所有段成本之和最大约 2e14注意第一行的“可先任意重排”。这四个字决定了整个题目的方向。重排之后段内最大值、最小值只取决于你选了哪些元素谁在左边谁在右边完全不影响成本所以这个题本质上是“把一堆数分成 k 组让组内极差之和最小”而不是“在保持原序的数组上切几个口子”。我在写暴力版本之前先把这两种情况分开就是因为实际踩过坑有的“分割”题允许重排有的不允许两者做法天差地别。你如果第一眼没确认这个条件后面代码写得再花哨都是白搭。1.2 我最初冒出来的暴力想法第一反应当然是动态规划。设 dp[i][j] 表示前 i 个数分成 j 段的最小总成本转移就是枚举上一段结束的位置 tdp[i][j] min(dp[t][j-1] cost(t1, i))其中 cost(l, r) 是区间 [l, r] 内最大值减最小值。如果 n 是 200这个做法完全没问题预处理一下区间最大最小值三层循环跑完收工。但这个题 n 能给到 1e5 量级k 又能取到 n那复杂度就是 O(n²k)别说是本地跑我样例都不太敢造大的。有经验的人会想到四边形不等式优化但那东西在“极差”这个区间函数上不一定满足单调性要求盲目上决策单调性优化是给自己挖坑。更关键的是即便优化到 O(nk)面对 nk1e5 这种输入依然超时。所以这个题一定存在面向数据范围的结构性结论不需要枚举分界点。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。如果 k1也就是不切一整段的成本就是 7。现在 k3我们需要在这个有序序列里切两刀。切在哪个位置等价于在两条相邻元素之间的“缝”上动刀。比如我切在 1|2 和 4|5 这两条缝得到三组[1] [2,4,5] [7,8][1] 的成本是 0[2,4,5] 的成本是 5-23[7,8] 的成本是 1总成本就是 0314。这时候你会发现总成本其实就是没被切掉的那些“缝”的数值之和。被切掉的两条缝它们的数值反而从总跨度里被剔除了。2.2 从样例里找出规律我们重新看排序后的数组和相邻差值相邻对1-22-44-55-77-8缝的值12121总跨度为 7。如果 k3要切两刀那两刀尽量切在最贵的两条缝上也就是两个“2”。把两条值为 2 的缝切掉之后剩下的缝值加起来正好是 1113。对应的切法是[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[i1] - b[i]任意一组 [L, R] 的成本为b[R] - b[L] g[L] g[L1] ... g[R-1]所以 k 组的总成本等于所有被某组覆盖的缝值之和。切开位置会割断相邻两个组的边界那一条缝不再被任何组覆盖。总共有 k-1 个切口所以总成本等于所有缝之和 - 被切开的那 k-1 条缝之和第一项是常数第二项越大总成本越小。要让第二项最大就直接取最大的 k-1 条缝。贪心成立不需要任何 dp。2.4 边界情况必须单独确认条件结果原因k 1答案就是排序后最大值-最小值一整段没有缝被切开k ≥ n答案是 0每个元素单独一段每段极差为 0所有元素相同答案是 0所有缝值均为 0数组有负数照常算排序后求差使用 64 位整数即可k1 和 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; vectorlong 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; } vectorlong 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元素绝对值最大 1e9n 最大 2e5总成本理论上限是 2e14 量级。这个数已经远超 32 位整数的范围。我用long long装数组和最终结果避免溢出。还有一种隐蔽溢出发生在“总跨度”这一步。如果数组里有 -1e9 和 1e9排序后a.back() - a.front()得到 2e9这个数值恰好能塞进 int但用它去减若干条缝值就可能变成负数之外的不确定值。稳妥起见从一开始就用long long。4. 如果题目不允许重排解法完全不同4.1 两种“分割”题怎么区分同样是“分割”不同题可能完全是两个物种。区分方法很简单看题目里有没有“连续子数组”“保持原顺序”“只能按下标顺序切”这类描述。如果有那不能排序如果允许分组、允许重排、只关心集合那才能走第 3 节的路。举一个很直观的例子数组 [5, 1, 9, 3]k2。如果允许重排最优分组是把 [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(t1, i) - min(t1, 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];k3 时切了 3 条缝等于分成了 4 段。答案自然偏小甚至会输出 0。这个错误本质上是没有理解“段数”和“刀数”的关系切 k 段只需要 k-1 刀。修好后我特意在本地加了一组测试输入 6 3 4 1 8 5 2 7正确输出应该是 3错误版本会输出 1。如果你也遇到答案比预期小的情况先检查是不是多切了一刀。5.2 n1 时脚本直接跪了我当时拿到手的第一版在 sort 之后立刻求 a.back()-a.front()然后开始枚举缝隙。当 n1 时a.back()-a.front()等于 0本来没问题但如果后面没有提前退出执行到 gaps 循环时就会出现对空数组的越界访问。后来我在代码里加了两道防线k1 时直接输出总跨度kn 时直接输出 0。这样 n1 的情况无论 k 是多少都不会走到缝隙数组相关逻辑。5.3 多组数据测试时没重置状态很多题库喜欢一直读到 EOF。我的测试脚本一开始用单组数据验证没问题后改成多组循环结果发现上一次排序留下的数据被带进了下一组。后来统一改成在循环内部定义vectorlong long a(n)和gaps让它们每次重新构造状态自然清空。代码短的情况下强烈建议用这种局部变量方式不要定义一个全局 vector 再手动 clear。排查技巧如果多组数据下偶尔出现奇怪大数优先怀疑是不是没有清空容器而不是去查算法本身。5.4 读题时以为“分割”就必须按原顺序这是我自己最痛的教训。我一开始把题理解成连续切分想了很久的单调队列优化 dp越写越复杂。后来重新读题面发现条件是“任意排列后再分割”瞬间意识到没必要 dp。从那以后拿到这种题我做的第一件事永远是确认“能不能重排”。如果原题描述很含糊我会直接写一个 n 很小的小暴力把两种解释都跑一遍看看哪个和样例对得上。这个习惯帮我避免了好几次在错误模型上浪费半天时间。6. 这类“分割题”的通用识别方法6.1 一个很实用的判断公式凡是段成本是“段内极差”“段内最大最小值之差”的分割题都可以先问自己一个问题如果把段内元素洗牌成本会变吗不会变那考虑排序、贪心、数轴缝隙会变那要考虑顺序相关 dp 或双指针。这个公式看着简单实际非常有效。因为很多分割题会把成本定义成“最大值减最小值”这就是在暗示你顺序不重要。一旦抓住这一点你就能把一道看似需要复杂数据结构的题化简成“排序后删掉最大缝隙”的结论。6.2 我对这类题的答题习惯最后分享一个我自己的习惯面对“分割”类题目我会先手算一组小样例比如 n5、k2把所有可能切法列出来。这个过程不会浪费太多时间但能让我把抽象的公式落到具体数字上。我在实际解题中发现很多人不是不会排序而是不敢把“切段”和“删缝”划等号。总觉得切段应该是在维护某段内部的信息实际上只要你把整段跨度全部摊开成相邻差值每一刀切在哪条缝上答案就完全由那条缝的值决定。这种思维转换比背下任何模板都重要。这道题也给我一个提醒压轴题未必需要高大上算法很多时候考验的是你愿不愿意把问题换一个角度重新描述一遍。搜索完所有已知模板找不到答案时退回到最原始的定义往往比继续堆优化更能找到出口。 
长河君 · 2026/10/24 8:35:30 · 阅读 1.2k 分割问题不用DP：排序后删掉最大缝隙，极差总和最小化
我是在一个在线题库里翻到这道题的编号排到 G题名却只有两个字分割。第一眼看上去标准的区间 dp 脸数据范围给得又不小差点就把我做自闭了。可等我真正把题读进去才发现这个题其实连 dp 数组都不需要核心就是一层等价转换把“切 k 段”想成“删掉 k-1 条缝”。想通这一点代码短到让人怀疑是不是骗样例复杂度也就是一次排序的事。因为原题面描述比较精简以下我按“分割”类题目最常见的完整设定展开给定 n 个整数你可以先任意重排这些数再把它切分成 k 个非空连续段每段成本是段内最大值减最小值目标是让 k 段成本总和最小。这个版本最能体现题目背后的算法思想也是我实际刷题时最常遇到的一种变体。如果你拿到的题明确要求不能重排、只能按下标连续切那请看第 4 节那完全是另一套做法。1. 拿到“分割”这个题名先别急着写代码1.1 先把题面翻译成人话原题没有给我多余的解释所以我先把可复现的完整设定写清楚参数含义典型范围n整数个数1e5 到 2e5k要切成的段数1 ≤ k ≤ na[i]原始整数绝对值 1e9 以内段成本段内最大值与最小值之差非负总成本所有段成本之和最大约 2e14注意第一行的“可先任意重排”。这四个字决定了整个题目的方向。重排之后段内最大值、最小值只取决于你选了哪些元素谁在左边谁在右边完全不影响成本所以这个题本质上是“把一堆数分成 k 组让组内极差之和最小”而不是“在保持原序的数组上切几个口子”。我在写暴力版本之前先把这两种情况分开就是因为实际踩过坑有的“分割”题允许重排有的不允许两者做法天差地别。你如果第一眼没确认这个条件后面代码写得再花哨都是白搭。1.2 我最初冒出来的暴力想法第一反应当然是动态规划。设 dp[i][j] 表示前 i 个数分成 j 段的最小总成本转移就是枚举上一段结束的位置 tdp[i][j] min(dp[t][j-1] cost(t1, i))其中 cost(l, r) 是区间 [l, r] 内最大值减最小值。如果 n 是 200这个做法完全没问题预处理一下区间最大最小值三层循环跑完收工。但这个题 n 能给到 1e5 量级k 又能取到 n那复杂度就是 O(n²k)别说是本地跑我样例都不太敢造大的。有经验的人会想到四边形不等式优化但那东西在“极差”这个区间函数上不一定满足单调性要求盲目上决策单调性优化是给自己挖坑。更关键的是即便优化到 O(nk)面对 nk1e5 这种输入依然超时。所以这个题一定存在面向数据范围的结构性结论不需要枚举分界点。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。如果 k1也就是不切一整段的成本就是 7。现在 k3我们需要在这个有序序列里切两刀。切在哪个位置等价于在两条相邻元素之间的“缝”上动刀。比如我切在 1|2 和 4|5 这两条缝得到三组[1] [2,4,5] [7,8][1] 的成本是 0[2,4,5] 的成本是 5-23[7,8] 的成本是 1总成本就是 0314。这时候你会发现总成本其实就是没被切掉的那些“缝”的数值之和。被切掉的两条缝它们的数值反而从总跨度里被剔除了。2.2 从样例里找出规律我们重新看排序后的数组和相邻差值相邻对1-22-44-55-77-8缝的值12121总跨度为 7。如果 k3要切两刀那两刀尽量切在最贵的两条缝上也就是两个“2”。把两条值为 2 的缝切掉之后剩下的缝值加起来正好是 1113。对应的切法是[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[i1] - b[i]任意一组 [L, R] 的成本为b[R] - b[L] g[L] g[L1] ... g[R-1]所以 k 组的总成本等于所有被某组覆盖的缝值之和。切开位置会割断相邻两个组的边界那一条缝不再被任何组覆盖。总共有 k-1 个切口所以总成本等于所有缝之和 - 被切开的那 k-1 条缝之和第一项是常数第二项越大总成本越小。要让第二项最大就直接取最大的 k-1 条缝。贪心成立不需要任何 dp。2.4 边界情况必须单独确认条件结果原因k 1答案就是排序后最大值-最小值一整段没有缝被切开k ≥ n答案是 0每个元素单独一段每段极差为 0所有元素相同答案是 0所有缝值均为 0数组有负数照常算排序后求差使用 64 位整数即可k1 和 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; vectorlong 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; } vectorlong 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元素绝对值最大 1e9n 最大 2e5总成本理论上限是 2e14 量级。这个数已经远超 32 位整数的范围。我用long long装数组和最终结果避免溢出。还有一种隐蔽溢出发生在“总跨度”这一步。如果数组里有 -1e9 和 1e9排序后a.back() - a.front()得到 2e9这个数值恰好能塞进 int但用它去减若干条缝值就可能变成负数之外的不确定值。稳妥起见从一开始就用long long。4. 如果题目不允许重排解法完全不同4.1 两种“分割”题怎么区分同样是“分割”不同题可能完全是两个物种。区分方法很简单看题目里有没有“连续子数组”“保持原顺序”“只能按下标顺序切”这类描述。如果有那不能排序如果允许分组、允许重排、只关心集合那才能走第 3 节的路。举一个很直观的例子数组 [5, 1, 9, 3]k2。如果允许重排最优分组是把 [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(t1, i) - min(t1, 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];k3 时切了 3 条缝等于分成了 4 段。答案自然偏小甚至会输出 0。这个错误本质上是没有理解“段数”和“刀数”的关系切 k 段只需要 k-1 刀。修好后我特意在本地加了一组测试输入 6 3 4 1 8 5 2 7正确输出应该是 3错误版本会输出 1。如果你也遇到答案比预期小的情况先检查是不是多切了一刀。5.2 n1 时脚本直接跪了我当时拿到手的第一版在 sort 之后立刻求 a.back()-a.front()然后开始枚举缝隙。当 n1 时a.back()-a.front()等于 0本来没问题但如果后面没有提前退出执行到 gaps 循环时就会出现对空数组的越界访问。后来我在代码里加了两道防线k1 时直接输出总跨度kn 时直接输出 0。这样 n1 的情况无论 k 是多少都不会走到缝隙数组相关逻辑。5.3 多组数据测试时没重置状态很多题库喜欢一直读到 EOF。我的测试脚本一开始用单组数据验证没问题后改成多组循环结果发现上一次排序留下的数据被带进了下一组。后来统一改成在循环内部定义vectorlong long a(n)和gaps让它们每次重新构造状态自然清空。代码短的情况下强烈建议用这种局部变量方式不要定义一个全局 vector 再手动 clear。排查技巧如果多组数据下偶尔出现奇怪大数优先怀疑是不是没有清空容器而不是去查算法本身。5.4 读题时以为“分割”就必须按原顺序这是我自己最痛的教训。我一开始把题理解成连续切分想了很久的单调队列优化 dp越写越复杂。后来重新读题面发现条件是“任意排列后再分割”瞬间意识到没必要 dp。从那以后拿到这种题我做的第一件事永远是确认“能不能重排”。如果原题描述很含糊我会直接写一个 n 很小的小暴力把两种解释都跑一遍看看哪个和样例对得上。这个习惯帮我避免了好几次在错误模型上浪费半天时间。6. 这类“分割题”的通用识别方法6.1 一个很实用的判断公式凡是段成本是“段内极差”“段内最大最小值之差”的分割题都可以先问自己一个问题如果把段内元素洗牌成本会变吗不会变那考虑排序、贪心、数轴缝隙会变那要考虑顺序相关 dp 或双指针。这个公式看着简单实际非常有效。因为很多分割题会把成本定义成“最大值减最小值”这就是在暗示你顺序不重要。一旦抓住这一点你就能把一道看似需要复杂数据结构的题化简成“排序后删掉最大缝隙”的结论。6.2 我对这类题的答题习惯最后分享一个我自己的习惯面对“分割”类题目我会先手算一组小样例比如 n5、k2把所有可能切法列出来。这个过程不会浪费太多时间但能让我把抽象的公式落到具体数字上。我在实际解题中发现很多人不是不会排序而是不敢把“切段”和“删缝”划等号。总觉得切段应该是在维护某段内部的信息实际上只要你把整段跨度全部摊开成相邻差值每一刀切在哪条缝上答案就完全由那条缝的值决定。这种思维转换比背下任何模板都重要。这道题也给我一个提醒压轴题未必需要高大上算法很多时候考验的是你愿不愿意把问题换一个角度重新描述一遍。搜索完所有已知模板找不到答案时退回到最原始的定义往往比继续堆优化更能找到出口。