科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载本文基于 leetcode/biweekly/122/d/README.md 官方题解笔记展开结合 d.go 仓库源码、d_test.go 测试用例与 copypasta/heap.go 通用对顶堆实现完整讲解 Biweekly Contest 122 第四题LC 题号 Divide an Array Into Subarrays With Minimum Cost II的两种高效解法双有序集合可看作对顶平衡树与对顶堆 懒删除。读完本文你将掌握在固定大小滑动窗口内动态维护前 k 小元素及其和这一核心技巧并能在 O(n log dist) 时间内解决同类区间 Top-K 问题。一、题意与核心转化为什么是滑动窗口内求前 k-1 小题目要求将数组nums划分为恰好k个非空子数组代价为每个子数组首元素之和求最小代价。官方题解笔记给出了两个关键观察第一段的第一个数是确定的即nums[0]第一段必然从下标 0 开始nums[0]必定计入代价且与后面的划分无关。只要确定了其余各段第一个数的位置划分方案就唯一确定。设第二段起点为p第三段起点为q……第k段起点为q且约束q-p ≤ dist保证第二段长度不超过dist。由此题目被转化为一个非常经典的结构化子问题在nums[1..n-1]上用一个大小固定为dist1的滑动窗口求窗口内前k-1小元素的和并对所有窗口位置取最小值最后加上nums[0]。窗口的物理含义是第二段的起点p一旦确定第二段内部除首元素外可以自由容纳的元素是nums[p1..pdist]长度dist为了让nums[p]尽量小同时允许第二段长度不超过dist等价于在窗口[p, pdist]共dist1个候选中选出k-1个元素作为后续各段的首元素。这也是仓库实现 d.go 直接写为slidingWindowKthSum(nums[1:], dist1, k-1)的原因——nums[1:]去掉确定的第一段窗口大小dist1需要选出k-1个最小的。对照阅读同一场比赛的第一题a/README.md是无距离约束的版本——两段起点可在[1, n-1]任意选直接取nums[1:]中最小两个即可而第四题因dist约束引入滑动窗口正是难度跃升的关键。二、方法一双有序集合对顶平衡树原文档的核心做法是仿照 LC 480「滑动窗口中位数」用两个有序集合维护窗口内前k-1小元素及其和。为方便计算先把k减一即k--表示需要在窗口中挑选的元素个数。2.1 初始化维护两个有序集合L和R约定L窗口内较小的k个数sumL记录L中元素之和R窗口内其余较大的数。初始化步骤如下把nums[1]到nums[dist1]即窗口[1, dist1]全部加入L保留L中最小的k个数把其余数移动到R此时sumL即为第一个窗口内前k小元素和ans sumL作为初始答案。2.2 滑动窗口的移动从i dist2开始每次窗口右移一个位置执行三步第 1 步移出窗口末尾元素out nums[i-dist-1]。若out在L中则从L移除sumL - out否则从R中移除。第 2 步移入新元素in nums[i]。若in小于L中的最大元素L的末元素则加入LsumL in否则加入R。这样新元素总会被放入正确的一半保持两个集合的相对序关系。第 3 步维护L的大小恒为k。移入移出可能破坏平衡若len(L) k-1从R中取出最小元素补入LsumL x若len(L) k1从L中取出最大元素移入RsumL - x。每次滑窗后用ans min(ans, sumL)更新答案。2.3 四种语言实现原文档完整代码Python3基于SortedListclass Solution: def minimumCost(self, nums: List[int], k: int, dist: int) - int: k - 1 sum_left sum(nums[:dist 2]) L SortedList(nums[1:dist 2]) R SortedList() def L2R() - None: x L.pop() nonlocal sum_left sum_left - x R.add(x) def R2L() - None: x R.pop(0) nonlocal sum_left sum_left x L.add(x) while len(L) k: L2R() ans sum_left for i in range(dist 2, len(nums)): # 移除 out out nums[i - dist - 1] if out in L: sum_left - out L.remove(out) else: R.remove(out) # 添加 in in_val nums[i] if in_val L[-1]: sum_left in_val L.add(in_val) else: R.add(in_val) # 维护大小 if len(L) k - 1: R2L() elif len(L) k 1: L2R() ans min(ans, sum_left) return ansC基于multisetclass Solution { public: long long minimumCost(vectorint nums, int k, int dist) { k--; long long sum reduce(nums.begin(), nums.begin() dist 2, 0LL); multisetint L(nums.begin() 1, nums.begin() dist 2), R; auto L2R []() { int x *L.rbegin(); sum - x; L.erase(L.find(x)); R.insert(x); }; auto R2L []() { int x *R.begin(); sum x; R.erase(R.find(x)); L.insert(x); }; while (L.size() k) { L2R(); } long long ans sum; for (int i dist 2; i nums.size(); i) { // 移除 out int out nums[i - dist - 1]; auto it L.find(out); if (it ! L.end()) { sum - out; L.erase(it); } else { R.erase(R.find(out)); } // 添加 in int in nums[i]; if (in *L.rbegin()) { sum in; L.insert(in); } else { R.insert(in); } // 维护大小 if (L.size() k - 1) { R2L(); } else if (L.size() k 1) { L2R(); } ans min(ans, sum); } return ans; } };Java基于TreeMap计数class Solution { public long minimumCost(int[] nums, int k, int dist) { k--; sumL nums[0]; for (int i 1; i dist 2; i) { sumL nums[i]; L.merge(nums[i], 1, Integer::sum); } sizeL dist 1; while (sizeL k) { l2r(); } long ans sumL; for (int i dist 2; i nums.length; i) { // 移除 out int out nums[i - dist - 1]; if (L.containsKey(out)) { sumL - out; sizeL--; removeOne(L, out); } else { removeOne(R, out); } // 添加 in int in nums[i]; if (in L.lastKey()) { sumL in; sizeL; L.merge(in, 1, Integer::sum); } else { R.merge(in, 1, Integer::sum); } // 维护大小 if (sizeL k - 1) { r2l(); } else if (sizeL k 1) { l2r(); } ans Math.min(ans, sumL); } return ans; } private long sumL; private int sizeL; private final TreeMapInteger, Integer L new TreeMap(); private final TreeMapInteger, Integer R new TreeMap(); private void l2r() { int x L.lastKey(); removeOne(L, x); sumL - x; sizeL--; R.merge(x, 1, Integer::sum); } private void r2l() { int x R.firstKey(); removeOne(R, x); sumL x; sizeL; L.merge(x, 1, Integer::sum); } private void removeOne(MapInteger, Integer m, int x) { int cnt m.get(x); if (cnt 1) { m.put(x, cnt - 1); } else { m.remove(x); } } }Go基于redblacktree红黑树即 d.go 中minimumCost2import github.com/emirpasic/gods/trees/redblacktree func minimumCost(nums []int, k, dist int) int64 { k-- L : redblacktree.NewWithIntComparator() R : redblacktree.NewWithIntComparator() add : func(t *redblacktree.Tree, x int) { c, ok : t.Get(x) if ok { t.Put(x, c.(int)1) } else { t.Put(x, 1) } } del : func(t *redblacktree.Tree, x int) { c, _ : t.Get(x) if c.(int) 1 { t.Put(x, c.(int)-1) } else { t.Remove(x) } } sumL : nums[0] for _, x : range nums[1 : dist2] { sumL x add(L, x) } sizeL : dist 1 l2r : func() { x : L.Right().Key.(int) sumL - x sizeL-- del(L, x) add(R, x) } r2l : func() { x : R.Left().Key.(int) sumL x sizeL del(R, x) add(L, x) } for sizeL k { l2r() } ans : sumL for i : dist 2; i len(nums); i { // 移除 out out : nums[i-dist-1] if _, ok : L.Get(out); ok { sumL - out sizeL-- del(L, out) } else { del(R, out) } // 添加 in in : nums[i] if in L.Right().Key.(int) { sumL in sizeL add(L, in) } else { add(R, in) } // 维护大小 if sizeL k-1 { r2l() } else if sizeL k1 { l2r() } ans min(ans, sumL) } return int64(ans) }需要注意 Go 版红黑树实现中add/del采用计数方式处理重复元素Put(x, 1)计数减到 0 时Remove因为nums元素可能重复单值有序集合无法直接支持。Java 的TreeMapInteger, Integer与removeOne同理。2.4 复杂度分析时间复杂度O(n·log dist)其中n为nums的长度。每次滑窗操作涉及常数次有序集合的插入/删除/取最值每次均为 O(log dist)。空间复杂度O(dist)两个有序集合最多各容纳 O(dist) 个元素。该复杂度远优于朴素做法——若不维护有序结构每次窗口移动都要重新排序代价为 O(n·dist·log dist)。三、方法二附对顶堆 懒删除有序集合需要平衡树级别的基础设施SortedList/multiset/TreeMap/redblacktree。若只有标准堆可用原文档提供了对顶堆 懒删除的 Go 实现这也是仓库 d.go 主函数minimumCost实际采用的路线。3.1 懒删除堆lazyHeap滑动窗口要求既能加元素也能删任意元素而堆只能高效删堆顶。懒删除的思路是del(v)不立即把v物理移出堆而是在哈希表todo中记录待删除次数todo[v]同时更新实际大小size和实际元素和sumpush(v)时若todo[v] 0说明这个值原本欠一次删除直接抵消todo[v]--无需真正入堆top()/pop()调用前执行_do()只要堆顶元素在todo中有欠账就逐个弹出抵消保证堆顶是真实存活的元素大堆Less(i,j)重写为IntSlice[i] IntSlice[j]最大堆最小堆则把所有元素取反后存入同一最大堆结构。type lazyHeap struct { sort.IntSlice todo map[int]int size int // 实际大小 sum int // 实际元素和 } func (h lazyHeap) Less(i, j int) bool { return h.IntSlice[i] h.IntSlice[j] } // 最大堆 func (h *lazyHeap) Push(v any) { h.IntSlice append(h.IntSlice, v.(int)) } func (h *lazyHeap) Pop() any { a : h.IntSlice; v : a[len(a)-1]; h.IntSlice a[:len(a)-1]; return v } func (h *lazyHeap) del(v int) { h.todo[v]; h.size--; h.sum - v } // 懒删除 func (h *lazyHeap) push(v int) { if h.todo[v] 0 { h.todo[v]-- } else { heap.Push(h, v) } h.size h.sum v } func (h *lazyHeap) pop() int { h.do(); h.size--; v : heap.Pop(h).(int); h.sum - v; return v } func (h *lazyHeap) top() int { h.do(); return h.IntSlice[0] } func (h *lazyHeap) do() { for h.Len() 0 h.todo[h.IntSlice[0]] 0 { h.todo[h.IntSlice[0]]-- heap.Pop(h) } }3.2 用对顶堆重写主流程左右两个lazyHeapl是最大堆存窗口内较小的k个数l.sum即前k小和r是最小堆存其余数元素全部取反。流程与原文档一致func minimumCost(nums []int, k int, dist int) int64 { k-- l : lazyHeap{todo: map[int]int{}} // 最大堆 r : lazyHeap{todo: map[int]int{}} // 最小堆所有元素取反 for _, x : range nums[1 : dist2] { l.push(x) } for l.size k { r.push(-l.pop()) } mn : l.sum for i : dist 2; i len(nums); i { // 移除 out out : nums[i-dist-1] if out l.top() { l.del(out) } else { r.del(-out) } // 添加 in in : nums[i] if in l.top() { l.push(in) } else { r.push(-in) } // 维护大小 if l.size k-1 { l.push(-r.pop()) } else if l.size k1 { r.push(-l.pop()) } mn min(mn, l.sum) } return int64(nums[0] mn) }判断out属于哪一半时用out l.top()而非out l.top()当有重复元素时二者都正确但与插入分支的配合更不易出错in与l.top()相等时放入r删除时相等的out也能走到l.del分支两个集合始终共享一致的判据。3.3 仓库中的通用化封装slidingWindowKthSum在 d.go 中作者把对顶堆方案进一步抽象成通用函数func slidingWindowKthSum(a []int, windowSize, k int) []int { n : len(a) kthSum : make([]int, n-windowSize1) h : kthHeap{lazyHeap{todo: map[int]int{}}, lazyHeap{todo: map[int]int{}}} for _, v : range a[:k] { h.l.push(v) } for _, v : range a[k:windowSize] { h.add(v) } kthSum[0] h.l.sum for r : windowSize; r n; r { l : r - windowSize // 前一个窗口的左端点 h.add(a[r]) h.del(a[l]) // 一定要先加再删 kthSum[l1] h.l.sum } return kthSum }细节要点输入a为去掉nums[0]后的序列windowSize dist1k k-1每个窗口位置i的kthSum[i]代表窗口a[i:iwindowSize]的前k小元素和注释强调一定要先加再删若先删后加del内部会因为l短暂缺员而触发r2l补位导致逻辑错乱先加后删则可保证l大小在两次操作间始终为k主函数只需int64(slices.Min(res) nums[0])d.go即对全部窗口位置取前k-1小和的最小值再加第一段首元素。kthHeap还提供了add/del封装d.goadd(v)内部用pushPop保证l大小不变——若v比l的堆顶小则替换堆顶并让旧堆顶进入r否则直接进r。四、测试验证仓库中的完整闭环该题在仓库内有完整的题解 测试 数据闭环路径分别为d.gominimumCost对顶堆主方案与minimumCost2红黑树对照实现两个版本d_test.go由模板工具生成的测试入口调用testutil.RunLeetCodeFuncWithFile(t, minimumCost, d.txt, 0)用d.txt中的样例驱动minimumCost并与期望值比对同时会通过随机数据对拍RunLeetCodeFuncWithFile内部实现见 testutil/leetcode.god.txt题目自带样例例如[1,3,2,6,4,2] 3 3 5 [10,1,2,2,2,1] 4 3 15 [10,8,18,9] 3 1 36每组样例依次为nums、k、dist、期望输出。三个样例分别覆盖了重复元素[1,3,2,6,4,2]、dist小于窗口容量的一般情况[10,1,2,2,2,1]、以及dist1的边界情况[10,8,18,9]此时第二段长度只能是 1答案退化为nums[0]nums[1]nums[2]36。读者可用go test ./leetcode/biweekly/122/d/在本地直接复现验证。五、仓库通用能力对顶堆在 copypasta 库中的沉淀本题解法并非孤立代码而是一套可复用的模板能力沉淀在算法模板库 copypasta/heap.go 中前缀中位数 / LC295heap.go单序列从左到右扫描对顶堆维护已扫描前缀的中位数滑动窗口中位数 / LC480heap.go滑动窗口内对顶堆求中位数并可用left.sum与right.sum直接计算左右半和是本题前 k 小和的直接先导滑动窗口前 k 小元素和heap.go即kthHeap的通用化版本注释中明确标注另见 treap_kthsum.go说明仓库还提供了 Treap 平衡树方案作为对顶堆的替代实现kthHeap还提供balance(k)heap.go方法可在不滑窗的场景下直接调整l的大小为k。从源码结构看这套lazyHeapkthHeap设计覆盖了中位数第 k 小前 k 小和三类典型查询配合定长滑动窗口可解决一大批 Top-K 区间问题。原文档提到的专题训练指向题单中「§5.7 对顶堆」一节仓库 leetcode/biweekly/122/a 的同场比赛第一题则是无dist约束的简化版本直接取两个最小值见 a/README.md二者对比阅读可以清晰体会从静态 Top-K 到滑动窗口 Top-K的复杂度递进。总结本题的核心方法论可以概括为三步把划分问题转化为滑动窗口子问题首段确定后其余k-1个段首元素必须在dist1大小的窗口中选出用对顶结构维护前 k 小左侧集合存窗口内较小的k个数并维护其和sumL右侧集合存其余元素滑窗时移出 移入 平衡大小三步循环选择合适的有序容器SortedList/multiset/TreeMap/redblacktree是开箱即用路线对顶堆 懒删除是仅有堆时的自建路线二者的复杂度同为 O(n·log dist)空间 O(dist)。掌握对顶堆/双有序集合 滑动窗口 懒删除这一组合你就能在 O(n log n) 级别的时间复杂度下从容应对各类区间内前 k 小元素及其和的题目这也是 copypasta/heap.go 中沉淀这套通用实现的初衷。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐代码分割求最小值双周赛 122 A 题「划分数组使总代价最小 I」的排序与线性双变量解法代码分割求最小值双周赛 122 A 题「划分数组使总代价最小 I」的排序与线性双变量解法 导读 本文围绕 LeetCode 第 122 场双周赛 A 题「Di科学计算大麦自动抢票工具 ticket-purchase从登录到提交订单一个脚本跑完整条链路大麦自动抢票工具 ticket purchase从登录到提交订单一个脚本跑完整条链路 ticket purchase 是一个用 Python 写的大麦自动抢GUI 自动化RPALeetCode 1343 题解滑动窗口与前缀和——求解「大小 k 且平均值 ≥ 阈值的子数组」数量LeetCode 1343 题解滑动窗口与前缀和——求解「大小 k 且平均值 ≥ 阈值的子数组」数量 本篇技术指南围绕 LeetCode 1343「Numbe示例工程教程上一篇oh-my-pi triage 命令GitHub Issue 自动分类与打标的可复制工作流下一篇Highlight.js 核心 API 完全指南从 highlight 到 configure 的源码级解析创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考