「放弹珠入袋」连续划分问题精讲：相邻和排序的贪心推导（codeforces-go 周赛 330 · C 题解析）

• 科学计算

本篇文章以算法竞赛模板库 codeforces-go 中 leetcode/weekly/330/c/README.md 这一周赛题解笔记为骨架，完整讲解 LeetCode 2551「放弹珠入袋」（Put Marbles in Bags，Weekly Contest 330 第 3 题）的建模、推导与五种语言实现。读完你将掌握一类「连续子数组划分求极差」问题的通用化处理手法：把划分边界的影响转化为相邻元素和，通过一次排序 O(n log n) 求解，并了解该题解在本仓库中的 Go 实现与自动化测试验证方式。

一、题目背景与问题建模

题目给定一个长度为 n 的数组weights和一个整数k，要求把弹珠（权重数组）恰好分成 k 个连续子数组（袋子），每个袋子由子数组两端（首尾）的弹珠权重之和作为该袋的分数，全部袋子的分数之和即为总分数。问最大总分数与最小总分数之差是多少。

题解笔记的第一步就是建模（对应原文档「提示 1」）：

问题相当于把weights划分成 k 个连续子数组，分数等于每个子数组的两端的值之和。

也就是说，表面上我们在「划分」，实际上分数只取决于划分点（切割边界）两侧的元素。这是一个非常典型的「贡献来自切割位置」问题：一旦想清楚分数由哪些元素贡献，就不必枚举所有划分方案。

二、核心推导：从「枚举划分」到「排序相邻和」

关键观察 1：两端元素必在分数中，且会互相抵消

无论怎么划分，weights[0]一定是第一个袋子的开头，weights[n-1]一定是最后一个袋子的结尾，所以它们必然同时出现在最大分数和最小分数中。题目要求的是两者之差，相减后这两项抵消（原文档「提示 2」）：

weights[0]和weights[n-1]一定在分数中，最大分数和最小分数相减，抵消了。

因此答案只与「内部切割位置」有关。

关键观察 2：内部切割等价于计入相邻元素对

把数组切成 k 段，需要 k-1 个内部切割点。考虑任意一个切割点，它位于某两个相邻元素weights[i]与weights[i+1]之间：weights[i]是左侧袋子的结尾，weights[i+1]是右侧袋子的开头，二者同时被计入分数（原文档「提示 2」后半句）：

上一个子数组的末尾和下一个子数组的开头一定同时在分数中。

于是「选 k-1 个切割点」等价于「从 n-1 对相邻元素weights[i]+weights[i+1]中选出 k-1 对」。对固定的一组切割点，总分数可以写成：

总分数 = weights[0] + weights[n-1] + (选中的 k-1 个相邻元素对之和) × 2

等等——这里需要精确核对：每个内部切割点对应一对相邻元素同时计入，但相邻的两个切割点会不会共用元素？分析发现，选中的相邻元素对互不重叠（切割点互不相邻时成立；若两个切割点相邻，则共用一个元素，但该元素会同时作为上一袋的结尾与下一袋的开头……），这正是本问题最精妙之处：最终结论是每个内部切割恰好对应一对相邻元素，二者各计一次，即分数贡献为weights[i] + weights[i+1]。最大分数与最小分数的差，只取决于「选哪 k-1 对相邻和」。

关键观察 3：极差 = 最大的 k-1 个相邻和 − 最小的 k-1 个相邻和

要让总分数最大，就选相邻和最大的 k-1 个切割点；要最小，就选相邻和最小的 k-1 个切割点。二者之差即为答案（原文档「提示 3」）：

把所有 n-1 个weights[i]+weights[i+1]算出来，排序，那么最大的 k-1 个数和最小的 k-1 个数相减，即为答案。

于是这道「划分 + 枚举」的题目被压缩为：计算 n-1 个相邻和 → 排序 → 前缀 k-1 个与后缀 k-1 个做差，时间复杂度 O(n log n)，空间 O(1)。

三、五种语言实现（继承原文档全部解法）

以下解法完整保留自 leetcode/weekly/330/c/README.md，均基于上述推导。

Python 3

class Solution: def putMarbles(self, weights: List[int], k: int) -> int: for i in range(len(weights) - 1): weights[i] += weights[i + 1] # 原地求前缀和 weights.pop() weights.sort() return sum(weights[len(weights) - k + 1:]) - sum(weights[:k - 1])

说明：第 2 行在原地把weights[i]改写为相邻和weights[i]+weights[i+1]（变量名注释为「原地求相邻和」更准确，即原地构造相邻元素对之和），第 3 行移除最后一个无意义的元素（weights[n-1]本身，它的相邻和已在倒数第二位算过），随后排序并分别累加最大 k-1 个与最小 k-1 个。

Java

class Solution { public long putMarbles(int[] weights, int k) { int n = weights.length; for (int i = 0; i < n - 1; i++) { weights[i] += weights[i + 1]; } Arrays.sort(weights, 0, n - 1); // 去掉最后一个数 long ans = 0; for (int i = 0; i < k - 1; i++) { ans += weights[n - 2 - i] - weights[i]; } return ans; } }

注意三点：① 对[0, n-1)区间排序，即跳过最后一个下标（其值已是原始weights[n-1]，不在相邻和集合内）；② 返回值用long，避免两两求和超出int范围；③ 求和循环直接把「最大的 k-1 个 − 最小的 k-1 个」合并在一次遍历里完成。

C++

class Solution { public: long long putMarbles(vector<int>& weights, int k) { int n = weights.size(); for (int i = 0; i < n - 1; i++) { weights[i] += weights[i + 1]; } sort(weights.begin(), weights.end() - 1); // 去掉最后一个数 long long ans = 0; for (int i = 0; i < k - 1; i++) { ans += weights[n - 2 - i] - weights[i]; } return ans; } };

C++（快速选择，O(n) 版本）

class Solution { public: long long putMarbles(vector<int>& weights, int k) { k--; // 注意这里减一了 if (k == 0) { return 0; } int n = weights.size() - 1; for (int i = 0; i < n; i++) { weights[i] += weights[i + 1]; } weights.pop_back(); long ans = 0; ranges::nth_element(weights, weights.begin() + k); for (int i = 0; i < k; i++) { ans -= weights[i]; } ranges::nth_element(weights, weights.end() - k); for (int i = 0; i < k; i++) { ans += weights[n - 1 - i]; } return ans; } };

这个版本展示了「只需要最大/最小的 k-1 个、不需要完整有序」的场景下，用nth_element（C++20 的ranges::nth_element）做两次分区：第一次找出最小的 k 个（含第 k 小），累加为负；第二次找出最大的 k 个，累加为正。整体复杂度降至 O(n)。注意开头的k--是为了把「切割数」转化为「要选出的相邻和个数」，k=0 时直接返回 0，这是边界兜底。

Go（本仓库实现）

func putMarbles(weights []int, k int) (ans int64) { for i, w := range weights[1:] { weights[i] += w } weights = weights[:len(weights)-1] slices.Sort(weights) for _, w := range weights[len(weights)-k+1:] { ans += int64(w) } for _, w := range weights[:k-1] { ans -= int64(w) } return }

说明：range weights[1:]配合下标 i，恰好把weights[i]更新为weights[i]+weights[i+1]；随后用切片截断weights[:len(weights)-1]丢弃末尾元素；slices.Sort是 Go 1.21+ 标准库泛型排序；两个循环分别累加最大的 k-1 个和减去最小的 k-1 个，累加时统一转成int64防止溢出，返回值通过命名返回值ans直接返回。

四、复杂度分析（继承原文档）

• 时间复杂度：O(n log n) 或 O(n)，其中 n 为weights的长度。普通排序做法为 O(n log n)；若使用快速选择算法（nth_element）只需要找第 k 小和第 n−k 大，可以做到 O(n)。
• 空间复杂度：O(1)，忽略排序的栈空间。

五、仓库源码级验证：实现、用例与测试框架

1. Go 题解文件

本仓库的对应实现位于 leetcode/weekly/330/c/c.go，与 README 中的 Go 解法完全一致：原地计算相邻和、切片截断、slices.Sort排序、两段循环做差。该文件属于package main，可直接作为单文件提交到周赛题解目录。

2. 测试数据文件

用例数据存放在 leetcode/weekly/330/c/c.txt，共三组（每组三行：输入数组、k、期望输出）：

[1,3,5,1] 2 4 [1, 3] 2 0 [1] 1 0

这三组用例恰好覆盖了三个典型场景：普通多袋划分（答案为 4）、n=2 且 k=2（只能各自成袋，最大=最小，答案为 0）、n=1 且 k=1（无法切割，答案为 0）。

3. 自动化测试入口

测试由 leetcode/weekly/330/c/c_test.go 驱动，它调用仓库统一的 LeetCode 题解测试工具：

func Test_c(t *testing.T) { targetCaseNum := 0 // -1 if err := testutil.RunLeetCodeFuncWithFile(t, putMarbles, "c.txt", targetCaseNum); err != nil { t.Fatal(err) } }

targetCaseNum := 0表示运行c.txt中全部用例；改为-1表示只运行最后一个用例（测试框架里targetCaseNum < 0时会换算成len(rawExamples) + 1）。测试注释中保留了题目来源：https://leetcode.cn/contest/weekly-contest-330/problems/put-marbles-in-bags/，即这是周赛 330 的 C 题。

4. 测试框架的底层机制

测试工具的核心实现位于 leetcode/testutil/leetcode.go。以本函数（两个int类型参数 + 一个int64返回值）为例，RunLeetCodeFuncWithFile的工作流程是：

1. 读取c.txt，按空行与空白字符清洗为行序列；
2. 通过反射（reflect.TypeOf(f).NumIn()/NumOut()）自动探测被测函数的输入参数个数和返回值个数，从而确定每组用例的行数tcSize = fNumIn + fNumOut，并校验「有效行数必须是 tcSize 的倍数」（leetcode.go）；
3. 对每组用例调用parseRawArg把文本[1,3,5,1]解析成[]int类型的实参（leetcode.go）；
4. 在RunLeetCodeFuncWithExamples中对每个用例执行函数并比较输出；当targetCaseNum == 0时还会用isTLE检测超时（leetcode.go）。

由此，只要把函数签名与测试文件写好、用例填进c.txt，新增或回归验证题解都无需手写断言逻辑——这也是本仓库周赛题解目录（如 leetcode/weekly/330 下的 a/b/c/d 四题）统一采用的组织方式。

六、边界情况与易错点小结

• k=1：无需任何切割，最大分数 = 最小分数 =weights[0] + weights[n-1]，答案为 0。快速选择版通过先k--后判断k == 0处理；排序版中k-1 = 0，两个循环都不执行，天然返回 0。
• 原地修改数组：五种实现都把原数组改写成相邻和，复用输入数组以达成 O(1) 额外空间。若题目后续还要用原数组，需先拷贝一份。
• 去掉最后一个元素：weights[i]+weights[i+1]只应生成 n-1 个值，最后一个下标n-1没有对应的右邻，必须从参与排序的集合中剔除（Python 的pop()、Java 的排序区间[0, n-1)、C++ 的end()-1、Go 的切片截断都是在做这件事）。
• 类型溢出：相邻和、以及 k-1 个相邻和累加都可能超出int（32 位）范围，因此 Java/C++ 用long/long long，Go 在累加时显式转为int64。

七、思维扩展：这类题的通用套路

本题是「连续划分 + 计算划分代价」问题的代表。从推导过程可以提炼出可复用的思考链：

1. 把「总代价」按元素或按切割位置拆分贡献，找出只与边界相邻元素有关的表达式；
2. 观察哪些项在最大/最小中必然同时出现（如两端元素），优先抵消；
3. 将「选择划分点」转化为「选择代价序列中的若干项」，用排序/堆/快速选择求极值。

这种「贡献在边界」「极差抵消常量项」的建模方式，在竞赛中常与贪心、堆（第 K 大/小）、快速选择等技巧配合出现，与仓库中 copypasta/ 目录下沉淀的排序、堆、快速选择等通用模板同属一类思维工具。若想进一步验证本题实现，可参照仓库统一的测试工具 leetcode/testutil/leetcode.go 自行组织更多随机用例进行回归。

• 科学计算