科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载本文围绕 LeetCode 第 126 场双周赛 B 题编号 3080Mark Elements on Array by Performing Queries展开完整讲解按值从小到大的索引排序 标记即清零的核心思路并给出 Python3 / Java / C / Go 四种语言实现、复杂度分析以及 codeforces-go 仓库中该题对应的测试驱动与样例验证读者学完后可独立复现并推广该技巧到同类按顺序选择最小未处理元素的问题中。题目背景与核心矛盾题意可以概括为给定正整数数组nums和若干查询queries每个查询给出(index, k)先标记nums[index]再额外标记当前 k 个最小的、尚未被标记的元素每次查询结束后返回剩余未标记元素之和。这道题的核心矛盾在于要按照元素值从小到大挑选未标记元素直觉上需要排序但查询又要求针对特定下标index做标记不能直接对nums排序排序会破坏下标与值的对应关系。解决方案是经典的排序索引index sort手法额外创建一个ids数组令ids[i] i然后按nums[ids[i]]从小到大对ids排序。这样既得到了值从小到大的全局顺序又保留了下标信息用于回答特定index的标记操作。核心思路拆解索引稳定排序 标记清零预处理构造有序索引ids sorted(range(n), keylambda i: nums[i])注意这里必须使用稳定排序stable sort对于值相同的元素排序后它们的下标依然按照下标从小到大排列若使用不稳定排序如快速排序则必须显式在比较函数中加入值相同按下标从小到大的次级规则。从仓库的 Go 实现可以看到这一细节的落地b.go 中使用了 Go 1.21 的slices.SortStableFuncslices.SortStableFunc(id, func(i, j int) int { return nums[i] - nums[j] })SortStableFunc保证比较结果相等的元素保持原始相对顺序恰好满足相同值按下标从小到大的需求这也是为什么模板库作者在 copypasta/common.go 等泛型排序场景中同样偏好稳定排序的原因该文件第 2461 行附近的注释即标注了or SortStableFunc的等价写法。标记 清零利用正整数性质免去哈希表题目保证nums中元素都是正数因此可以做一个精妙的简化初始化s为nums元素之和标记一个数就是把它置为 0同时在s中减去它的值判断是否已被标记只需检查nums[i] 00 表示已标记。这样无需额外的visited数组或哈希表空间更省、判断更快。每轮查询的处理流程设ids已按值升序排好维护一个只前进不回溯的指针j初始为 0标记指定下标s - nums[index]然后nums[index] 0标记 k 个最小未标记元素从j开始沿ids扫描跳过已被标记的值为 0元素遇到未标记的值 0就清零并累计减去指针j始终单调递增因此整个流程中每个下标最多被扫描一次记录当前s作为本次查询的答案。指针j的单调性是该算法能从每轮从头找 k 个最小的 O(n·q) 降到 O(n log n) 的关键ids已经全局有序被标记过的元素只会越来越多游标只会向右移动。多语言实现原文完整继承以下四种语言实现完全等价均来自原解题文档。Python3class Solution: def unmarkedSumArray(self, nums: List[int], queries: List[List[int]]) - List[int]: n len(nums) s sum(nums) ids sorted(range(n), keylambda i: nums[i]) # 稳定排序 ans [] j 0 for i, k in queries: s - nums[i] nums[i] 0 # 标记 while j n and k: i ids[j] if nums[i]: # 没有被标记 s - nums[i] nums[i] 0 k - 1 j 1 ans.append(s) return ansPython 的sorted是稳定排序配合keylambda i: nums[i]即可得到值升序、同值按下标升序的索引序列。Javaclass Solution { public long[] unmarkedSumArray(int[] nums, int[][] queries) { int n nums.length; long s 0; Integer[] ids new Integer[n]; for (int i 0; i n; i) { s nums[i]; ids[i] i; } Arrays.sort(ids, (i, j) - nums[i] - nums[j]); // 稳定排序 long[] ans new long[queries.length]; int j 0; for (int qi 0; qi queries.length; qi) { int[] q queries[qi]; int i q[0]; int k q[1]; s - nums[i]; nums[i] 0; // 标记 for (; j n k 0; j) { i ids[j]; if (nums[i] 0) { // 没有被标记 s - nums[i]; nums[i] 0; k--; } } ans[qi] s; } return ans; } }注意 Java 中nums[i] - nums[j]作为比较器时若差值可能溢出本题值域内安全需改用Integer.compare同时返回值必须用long[]承接可能超过 int 范围的元素和。Cclass Solution { public: vectorlong long unmarkedSumArray(vectorint nums, vectorvectorint queries) { int n nums.size(); long long s accumulate(nums.begin(), nums.end(), 0LL); vectorint ids(n); iota(ids.begin(), ids.end(), 0); ranges::stable_sort(ids, { return nums[i] nums[j]; }); vectorlong long ans; int j 0; for (auto q : queries) { int i q[0], k q[1]; s - nums[i]; nums[i] 0; // 标记 for (; j n k; j) { i ids[j]; if (nums[i] 0) { // 没有被标记 s - nums[i]; nums[i] 0; k--; } } ans.push_back(s); } return ans; } };C20 的ranges::stable_sort直接支持稳定排序iota用于快速生成0..n-1的索引序列。Go仓库工程化版本func unmarkedSumArray(nums []int, queries [][]int) []int64 { s, n : 0, len(nums) id : make([]int, n) for i, x : range nums { s x id[i] i } slices.SortStableFunc(id, func(i, j int) int { return nums[i] - nums[j] }) ans : make([]int64, len(queries)) j : 0 for qi, p : range queries { i, k : p[0], p[1] s - nums[i] nums[i] 0 // 标记 for ; j n k 0; j { i : id[j] if nums[i] 0 { // 没有标记 s - nums[i] nums[i] 0 k-- } } ans[qi] int64(s) } return ans }复杂度分析时间复杂度O(n log n)其中 n 为nums的长度。瓶颈在排序上排序之后每轮查询中指针j单调右移全部查询对ids的总扫描次数不超过 n。空间复杂度O(n)忽略返回值空间。ids数组占用 O(n)其余变量为常数空间。由于j不回溯即使有 q 个查询标记k 个最小未标记元素的总代价仍为 O(n)这正是该解法在 n、q 均达到较大规模时依然高效的原因。仓库中的工程化落地测试驱动与样例验证本题在 codeforces-go 仓库中不是孤立的一段代码而是被完整的 LeetCode 测试流水线覆盖可用于本地复现验证。目录结构与三个文件的分工leetcode/biweekly/126/b/目录下共四个文件README.md原解题文档即本文主体内容来源b.go解法实现即上文 Go 版本b.txt测试用例数据文件b_test.go测试入口。其中 b_test.go 的测试驱动如下func Test_b(t *testing.T) { if err : testutil.RunLeetCodeFuncWithFile(t, unmarkedSumArray, b.txt, 0); err ! nil { t.Fatal(err) } } // https://leetcode.cn/contest/biweekly-contest-126/problems/mark-elements-on-array-by-performing-queries/ // https://leetcode.cn/problems/mark-elements-on-array-by-performing-queries/RunLeetCodeFuncWithFile定义在 leetcode/testutil/leetcode.go它读取b.txt去掉空行后按输入行数 函数入参个数 出参个数的规则切分测试数据再借助反射parseRawArg/toRawString将文本自动解析为 Go 类型并逐条比对输出同时支持 TLE 检测超时阈值在 leetcode/testutil/config.go 中默认为2 * time.Second。这套机制让每场周赛/双周赛题目落地为可回归的测试用例变成流水线操作——双周赛测试的批量生成入口见 copypasta/template/leetcode/generator_test.go 中的TestBiweekly。用 b.txt 中的样例做逐步推演b.txt包含两组用例第一组原文注释未给出推导这里补全为nums [1,2,2,1,2,3,1] # s 12 queries [[1,2],[3,3],[4,2]] answer [8,3,0]ids稳定排序后为[0,3,6,1,2,4,5]值为 1 的三个下标 0/3/6 排最前且按下标升序查询[1,2]先标记下标 1值 2s 10再按 ids 依次标记下标 0值 1与下标 3值 1s 8查询[3,3]下标 3 已被标记值 0s不变仍为 8指针继续沿 ids 扫描依次标记下标 6值 1、下标 2值 2、下标 4值 2s 3查询[4,2]下标 4 已是 0ids 中剩余未标记的只有下标 5值 3标记后s 0。第二组用例[1,4,2,3][[0,1]]则验证了目标下标恰好也是最小元素的情形先标记下标 0值 1随后沿 ids 标记的仍是下标 0已被标记则跳过与下标 2值 2最终s 7。边界情况与易错点小结稳定排序的必要性相同值的下标必须按下标从小到大标记直接快排会破坏该约束若用不稳定排序必须补次级比较条件值相同比下标。清零即标记依赖正整数前提若数组允许负数或 0该技巧失效需要引入visited数组。指针 j 的推进位置无论当前ids[j]是否已被标记j都要自增否则死循环外层还需j n防越界当所有元素都被标记后k 可能仍大于 0此时直接结束循环。求和溢出Java / C / Go 的实现均使用 64 位整数long/long long/int64承载元素和避免大测试数据下 int 溢出。延伸相关题单主题该解法属于按顺序处理最小未标记元素的通用技巧。原文档附带的相关题单主题包括滑动窗口定长/不定长/多指针、二分算法二分答案/最小化最大值/最大化最小值/第 K 小、单调栈矩形系列/字典序最小/贡献法、网格图DFS/BFS/综合应用、位运算基础/性质/拆位/试填/恒等式/贪心/脑筋急转弯、图论算法DFS/BFS/拓扑排序/最短路/最小生成树/二分图/基环树/欧拉路径等原文档以链接形式给出读者可按需在个人主页讨论区检索对应合集。将索引排序 单调指针的模式迁移到这些场景中往往能让每次取当前最小未处理项类问题的时间复杂度从 O(nq) 降到 O(n log n)。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐LeetCode 977 有序数组的平方Squares of a Sorted Array全解从 O(n log n) 排序到 O(n) 双指针LeetCode 977 有序数组的平方Squares of a Sorted Array全解从 O n log n 排序到 O n 双指针 本篇技术指南示例工程教程3分钟快速解决Cursor试用限制让你的AI编程助手重新焕发活力3分钟快速解决Cursor试用限制让你的AI编程助手重新焕发活力 你是否曾经在使用Cursor AI编辑器时突然遇到此机器已使用过多免费试用账户的提示开发工具CLIRufus 制作 U 盘启动盘指南3 步搞定 Windows 安装盘Rufus 制作 U 盘启动盘指南3 步搞定 Windows 安装盘 深夜系统崩了你翻出抽屉里的旧 U 盘准备重装开机启动菜单里却没有 U 盘选项——它只桌面应用开发工具上一篇Mac 菜单栏管理工具 Ice一键收纳拥挤图标5 分钟还你清爽桌面下一篇D2DX补丁深度解析破解25帧封印、撕掉黑边的《暗黑破坏神2》现代化引擎创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考