)
科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载本篇文章以算法竞赛模板库 codeforces-go 中 leetcode/weekly/330/c/README.md 这一周赛题解笔记为骨架完整讲解 LeetCode 2551「放弹珠入袋」Put Marbles in BagsWeekly 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[i1]之间weights[i]是左侧袋子的结尾weights[i1]是右侧袋子的开头二者同时被计入分数原文档「提示 2」后半句上一个子数组的末尾和下一个子数组的开头一定同时在分数中。于是「选 k-1 个切割点」等价于「从 n-1 对相邻元素weights[i]weights[i1]中选出 k-1 对」。对固定的一组切割点总分数可以写成总分数 weights[0] weights[n-1] (选中的 k-1 个相邻元素对之和) × 2等等——这里需要精确核对每个内部切割点对应一对相邻元素同时计入但相邻的两个切割点会不会共用元素分析发现选中的相邻元素对互不重叠切割点互不相邻时成立若两个切割点相邻则共用一个元素但该元素会同时作为上一袋的结尾与下一袋的开头……这正是本问题最精妙之处最终结论是每个内部切割恰好对应一对相邻元素二者各计一次即分数贡献为weights[i] weights[i1]。最大分数与最小分数的差只取决于「选哪 k-1 对相邻和」。关键观察 3极差 最大的 k-1 个相邻和 − 最小的 k-1 个相邻和要让总分数最大就选相邻和最大的 k-1 个切割点要最小就选相邻和最小的 k-1 个切割点。二者之差即为答案原文档「提示 3」把所有 n-1 个weights[i]weights[i1]算出来排序那么最大的 k-1 个数和最小的 k-1 个数相减即为答案。于是这道「划分 枚举」的题目被压缩为计算 n-1 个相邻和 → 排序 → 前缀 k-1 个与后缀 k-1 个做差时间复杂度 O(n log n)空间 O(1)。三、五种语言实现继承原文档全部解法以下解法完整保留自 leetcode/weekly/330/c/README.md均基于上述推导。Python 3class 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[i1]变量名注释为「原地求相邻和」更准确即原地构造相邻元素对之和第 3 行移除最后一个无意义的元素weights[n-1]本身它的相邻和已在倒数第二位算过随后排序并分别累加最大 k-1 个与最小 k-1 个。Javaclass 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 个」合并在一次遍历里完成。Cclass Solution { public: long long putMarbles(vectorint 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(vectorint 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_elementC20 的ranges::nth_element做两次分区第一次找出最小的 k 个含第 k 小累加为负第二次找出最大的 k 个累加为正。整体复杂度降至 O(n)。注意开头的k--是为了把「切割数」转化为「要选出的相邻和个数」k0 时直接返回 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)-k1:] { ans int64(w) } for _, w : range weights[:k-1] { ans - int64(w) } return }说明range weights[1:]配合下标 i恰好把weights[i]更新为weights[i]weights[i1]随后用切片截断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、n2 且 k2只能各自成袋最大最小答案为 0、n1 且 k1无法切割答案为 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的工作流程是读取c.txt按空行与空白字符清洗为行序列通过反射reflect.TypeOf(f).NumIn()/NumOut()自动探测被测函数的输入参数个数和返回值个数从而确定每组用例的行数tcSize fNumIn fNumOut并校验「有效行数必须是 tcSize 的倍数」leetcode.go对每组用例调用parseRawArg把文本[1,3,5,1]解析成[]int类型的实参leetcode.go在RunLeetCodeFuncWithExamples中对每个用例执行函数并比较输出当targetCaseNum 0时还会用isTLE检测超时leetcode.go。由此只要把函数签名与测试文件写好、用例填进c.txt新增或回归验证题解都无需手写断言逻辑——这也是本仓库周赛题解目录如 leetcode/weekly/330 下的 a/b/c/d 四题统一采用的组织方式。六、边界情况与易错点小结k1无需任何切割最大分数 最小分数 weights[0] weights[n-1]答案为 0。快速选择版通过先k--后判断k 0处理排序版中k-1 0两个循环都不执行天然返回 0。原地修改数组五种实现都把原数组改写成相邻和复用输入数组以达成 O(1) 额外空间。若题目后续还要用原数组需先拷贝一份。去掉最后一个元素weights[i]weights[i1]只应生成 n-1 个值最后一个下标n-1没有对应的右邻必须从参与排序的集合中剔除Python 的pop()、Java 的排序区间[0, n-1)、C 的end()-1、Go 的切片截断都是在做这件事。类型溢出相邻和、以及 k-1 个相邻和累加都可能超出int32 位范围因此 Java/C 用long/long longGo 在累加时显式转为int64。七、思维扩展这类题的通用套路本题是「连续划分 计算划分代价」问题的代表。从推导过程可以提炼出可复用的思考链把「总代价」按元素或按切割位置拆分贡献找出只与边界相邻元素有关的表达式观察哪些项在最大/最小中必然同时出现如两端元素优先抵消将「选择划分点」转化为「选择代价序列中的若干项」用排序/堆/快速选择求极值。这种「贡献在边界」「极差抵消常量项」的建模方式在竞赛中常与贪心、堆第 K 大/小、快速选择等技巧配合出现与仓库中 copypasta/ 目录下沉淀的排序、堆、快速选择等通用模板同属一类思维工具。若想进一步验证本题实现可参照仓库统一的测试工具 leetcode/testutil/leetcode.go 自行组织更多随机用例进行回归。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐codeforces-go 题解最长相邻不等分组子序列 I —— 连续相同段贪心取一个的 O(n) 解法codeforces go 题解最长相邻不等分组子序列 I —— 连续相同段贪心取一个的 O n 解法 导读 本文讲解 LeetCode 第 115 场双周赛科学计算codeforces-go 题解精讲LeetCode 第 118 场双周赛 B 题「最大化网格正方形洞的面积」—— 贪心与最长连续序列codeforces go 题解精讲LeetCode 第 118 场双周赛 B 题「最大化网格正方形洞的面积」—— 贪心与最长连续序列 本篇技术指南以 cod科学计算codeforces-go 仓库题解精讲LeetCode 1200 最小绝对差Minimum Absolute Difference——排序后相邻扫描的一趟贪心法codeforces go 仓库题解精讲LeetCode 1200 最小绝对差Minimum Absolute Difference——排序后相邻扫描的一科学计算上一篇【亲测免费】 js-confetti轻量级JavaScript五彩纸屑特效库下一篇oidc-client-ts 开源项目教程创作声明:本文部分内容由AI辅助生成(AIGC),仅供参考