科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载本题解对应仓库文档 leetcode/weekly/274/c/2126.md配套源码与测试位于 leetcode/weekly/274/c/c.go 与 leetcode/weekly/274/c/c_test.go。本仓库是算法竞赛模板库codeforces-go每周力扣周赛题解都会沉淀为「题目 markdown 多语言实现 测试用例」三件套本文以 2126 题为样本完整讲解贪心策略的两种严谨证明以及一种把排序优化掉、按二进制长度分组达成 O(n) 的进阶做法。一、题目回顾与贪心直觉LeetCode 2126 是第 274 场周赛的第 3 题Destroying Asteroids题意可从前缀为asteroidsDestroyed(mass int, asteroids []int) bool的源码签名中还原给定行星初始质量mass与一个小行星质量数组asteroids每次可以摧毁一颗质量不超过当前行星质量的小行星摧毁后行星吸收其质量判断是否存在某种摧毁顺序使得所有小行星都能被摧毁能则返回true否则返回false。直觉很直接先摧毁质量小的小行星用它们把行星喂大之后再对付质量大的。因为摧毁小质量对象的门槛低且获得的回报是纯收益不存在先吃大的会撑到的约束所以贪心路径是从小到大能摧就摧。但直觉归直觉这道题的关键难点在于为什么局部最优的顺序从小到大一定全局最优原文档给出了一个严格命题和两种证明方法。二、核心命题为什么从小到大是最优的命题如果存在一种顺序 A 可以摧毁所有小行星那么按照质量从小到大的顺序摧毁也一定可以摧毁所有小行星。换言之递增顺序是最容易成功的候选顺序——它要么成功要么说明根本没有任何顺序能成功。这样就把是否存在某种顺序的判定问题化简为检验递增顺序这一个模拟问题。证法一交换论证类似冒泡排序如果 A 已经是递增的命题显然成立。如果 A 不是递增的即存在相邻逆序对 Aᵢ Aᵢ₊₁设摧毁 Aᵢ 之前行星质量为 M则有M ≥ Aᵢ否则 Aᵢ 根本摧不动M Aᵢ ≥ Aᵢ₊₁否则摧毁 Aᵢ 后卡死在 Aᵢ₊₁。现在交换这两颗小行星的顺序由于 M ≥ Aᵢ Aᵢ₊₁所以可以先摧毁 Aᵢ₊₁由于 M ≥ Aᵢ所以 M Aᵢ₊₁ ≥ Aᵢ 更加成立可以后摧毁 Aᵢ。于是反复交换 A 中逆序的相邻小行星这正是冒泡排序的过程把 A 排成递增的全程仍然可以摧毁所有小行星。命题得证。证法二逆否命题证明原命题的逆否命题如果按质量从小到大记作 B无法摧毁所有小行星那么不存在任何可以摧毁所有小行星的顺序。设 i 是满足 Bᵢ mass Σⱼ₌₀^{i-1} Bⱼ 的最小下标即排序后第一个啃不动的位置此时行星质量恰为前 i 颗质量之和加初始质量。把 B 分成两个集合S {B₀, B₁, …, Bᵢ₋₁}质量较小的部分T {Bᵢ, Bᵢ₊₁, …, Bₙ₋₁}质量较大的部分。设 x 是任意顺序中我们尝试摧毁的第一颗属于 T 的小行星那么摧毁 x 之前行星质量至多为 M mass Σ_{m∈S} m因为排在 x 之前被摧毁的只能是 S 中的元素。由于 M Bᵢ ≤ Bᵢ₊₁ ≤ … ≤ Bₙ₋₁M 小于 T 中任何一颗小行星的质量我们无法摧毁 x。既然任何顺序在 T 上都必定卡死所以不存在可以摧毁所有小行星的顺序。两种证明从正反两面锁死了结论排序后逐个模拟就是这道题的完整解法。三、排序解法先排序再模拟依据上述命题把asteroids从小到大排序然后检查该顺序能否摧毁所有小行星即可。只要某一步行星质量小于当前最小剩余小行星的质量立即返回false。class Solution: def asteroidsDestroyed(self, mass: int, asteroids: List[int]) - bool: asteroids.sort() for x in asteroids: if mass x: # 无法摧毁小行星 x return False mass x # 获得这颗小行星的质量 return Trueclass Solution { public boolean asteroidsDestroyed(int mass, int[] asteroids) { Arrays.sort(asteroids); long m mass; for (int x : asteroids) { if (m x) { // 无法摧毁小行星 x return false; } m x; // 获得这颗小行星的质量 } return true; } }class Solution { public: bool asteroidsDestroyed(int mass, vectorint asteroids) { ranges::sort(asteroids); long long m mass; for (int x : asteroids) { if (m x) { // 无法摧毁小行星 x return false; } m x; // 获得这颗小行星的质量 } return true; } };int cmp(const void* a, const void* b) { return *(int*)a - *(int*)b; } bool asteroidsDestroyed(int mass, int* asteroids, int asteroidsSize) { qsort(asteroids, asteroidsSize, sizeof(int), cmp); long long m mass; for (int i 0; i asteroidsSize; i) { int x asteroids[i]; if (m x) { // 无法摧毁小行星 x return false; } m x; // 获得这颗小行星的质量 } return true; }func asteroidsDestroyed(mass int, asteroids []int) bool { slices.Sort(asteroids) for _, x : range asteroids { if mass x { // 无法摧毁小行星 x return false } mass x // 获得这颗小行星的质量 } return true }var asteroidsDestroyed function(mass, asteroids) { asteroids.sort((a, b) a - b); for (const x of asteroids) { if (mass x) { // 无法摧毁小行星 x return false; } mass x; // 获得这颗小行星的质量 } return true; };impl Solution { pub fn asteroids_destroyed(mass: i32, mut asteroids: Veci32) - bool { asteroids.sort_unstable(); let mut mass mass as i64; for x in asteroids { if mass x as i64 { // 无法摧毁小行星 x return false; } mass x as i64; // 获得这颗小行星的质量 } true } }复杂度分析时间复杂度O(n log n)其中 n 是asteroids的长度瓶颈在排序上空间复杂度O(1)忽略排序的栈开销。一个必须注意的工程细节Java/C/C/Rust 中行星质量必须用long/long long/i64承接。n 可达 10⁵、单颗质量可达 10⁹累加和远超 int32 上限Go 的int在主流平台是 64 位Python 与 JS 自带大整数则无此顾虑。仓库 Go 实现 c.go 中的asteroidsDestroyed1正是该解法的落地版本。四、优化按二进制长度分组免排序排序解法的 O(n log n) 已经足以通过本题但原文档给出了一种更优雅的线性做法基于一个简单但强大的事实一个 ≥ 2ᵏ 的数加上另一个 ≥ 2ᵏ 的数和一定 ≥ 2ᵏ⁺¹。基于这一事实可以把asteroids中的元素按照二进制长度分组在 [2⁰, 2¹) 中的数分到同一组在 [2¹, 2²) 中的数分到同一组在 [2², 2³) 中的数分到同一组……设行星质量为 M。如果 M ≥ 组内最小值那么 M 加上组内最小值后结果一定大于组内的每个值因为组内元素都 2ᵏ⁺¹而 M min ≥ 2ᵏ 2ᵏ 2ᵏ⁺¹所以这一组的质量可以全部一次性加到 M 中。这样一来我们只需统计每一组的最小值和元素和无需对组内元素排序按组号从小到大处理即可。组号上限是最大值max(asteroids)的二进制长度记作 log U因此扫描所有组只需 O(log U) 次。按二进制长度分组的实现class Solution: def asteroidsDestroyed(self, mass: int, asteroids: List[int]) - bool: max_width max(asteroids).bit_length() mn [inf] * max_width sum_ [0] * max_width for x in asteroids: i x.bit_length() - 1 mn[i] min(mn[i], x) sum_[i] x for m, s in zip(mn, sum_): if m inf: continue if mass m: # 无法摧毁这组的任意小行星 return False mass s # 获得这组小行星的质量 return Trueclass Solution: def asteroidsDestroyed(self, mass: int, asteroids: List[int]) - bool: mn defaultdict(lambda: inf) sum_ defaultdict(int) mask 0 for x in asteroids: i x.bit_length() - 1 mn[i] min(mn[i], x) sum_[i] x mask | 1 i while mask: lowbit mask -mask # mask 的最低位 i lowbit.bit_length() - 1 if mass mn[i]: # 无法摧毁这组的任意小行星 return False mass sum_[i] # 获得这组小行星的质量 mask ^ lowbit # 移除 mask 的最低位 return Trueclass Solution { public boolean asteroidsDestroyed(int mass, int[] asteroids) { int mx 0; for (int x : asteroids) { mx Math.max(mx, x); } int maxWidth 32 - Integer.numberOfLeadingZeros(mx); long[] sum new long[maxWidth]; int[] mn new int[maxWidth]; Arrays.fill(mn, Integer.MAX_VALUE); for (int x : asteroids) { int i 31 - Integer.numberOfLeadingZeros(x); // x 的二进制长度减一 sum[i] x; mn[i] Math.min(mn[i], x); } long m mass; for (int i 0; i maxWidth; i) { if (mn[i] Integer.MAX_VALUE) { continue; } if (m mn[i]) { // 无法摧毁这组的任意小行星 return false; } m sum[i]; // 获得这组小行星的质量 } return true; } }class Solution { public: bool asteroidsDestroyed(int mass, vectorint asteroids) { int max_width bit_width(1u * ranges::max(asteroids)); vectorint mn(max_width, INT_MAX); vectorlong long sum(max_width); for (int x : asteroids) { int i bit_width(1u * x) - 1; mn[i] min(mn[i], x); sum[i] x; } long long m mass; for (int i 0; i max_width; i) { if (mn[i] INT_MAX) { continue; } if (m mn[i]) { // 无法摧毁这组的任意小行星 return false; } m sum[i]; // 获得这组小行星的质量 } return true; } };bool asteroidsDestroyed(int mass, int* asteroids, int asteroidsSize) { int mx 0; for (int i 0; i asteroidsSize; i) { mx MAX(mx, asteroids[i]); } int max_width 32 - __builtin_clz(mx); long long* sum calloc(max_width, sizeof(long long)); int* mn malloc(max_width * sizeof(int)); for (int i 0; i max_width; i) { mn[i] INT_MAX; } for (int i 0; i asteroidsSize; i) { int x asteroids[i]; int j 31 - __builtin_clz(x); // x 的二进制长度减一 sum[j] x; mn[j] MIN(mn[j], x); } long long m mass; for (int i 0; i max_width; i) { if (mn[i] INT_MAX) { continue; } if (m mn[i]) { // 无法摧毁这组的任意小行星 free(mn); free(sum); return false; } m sum[i]; // 获得这组小行星的质量 } free(mn); free(sum); return true; }func asteroidsDestroyed(mass int, asteroids []int) bool { maxWidth : bits.Len(uint(slices.Max(asteroids))) sum : make([]int, maxWidth) mn : make([]int, maxWidth) for i : range mn { mn[i] math.MaxInt } for _, x : range asteroids { i : bits.Len(uint(x)) - 1 sum[i] x mn[i] min(mn[i], x) } for i, m : range mn { if m math.MaxInt { continue } if mass m { // 无法摧毁这组的任意小行星 return false } mass sum[i] // 获得这组小行星的质量 } return true }var asteroidsDestroyed function(mass, asteroids) { const maxWidth 32 - Math.clz32(Math.max(...asteroids)); const mn Array(maxWidth).fill(Infinity); const sum Array(maxWidth).fill(0); for (const x of asteroids) { const i 31 - Math.clz32(x); // x 的二进制长度减一 mn[i] Math.min(mn[i], x); sum[i] x; } for (let i 0; i maxWidth; i) { if (mn[i] Infinity) { continue; } if (mass mn[i]) { // 无法摧毁这组的任意小行星 return false; } mass sum[i]; // 获得这组小行星的质量 } return true; };impl Solution { pub fn asteroids_destroyed(mass: i32, asteroids: Veci32) - bool { let mx *asteroids.iter().max().unwrap(); let max_width 32 - mx.leading_zeros() as usize; let mut mn vec![i32::MAX; max_width]; let mut sum vec![0; max_width]; for x in asteroids { let i 31 - x.leading_zeros() as usize; // x 的二进制长度减一 mn[i] mn[i].min(x); sum[i] x as i64; } let mut mass mass as i64; for (m, s) in mn.into_iter().zip(sum.into_iter()) { if m i32::MAX { continue; } if mass m as i64 { // 无法摧毁这组的任意小行星 return false; } mass s; // 获得这组小行星的质量 } true } }Python3 写法二额外引入了一个技巧用mask的二进制位记录哪些组非空然后通过lowbit mask -mask依次取出最低位、用mask ^ lowbit移除它从而只遍历实际存在的组把复杂度从 O(n log U) 进一步压到严格的 O(n)。复杂度分析时间复杂度O(n log U) 或 O(n)其中 n 是asteroids的长度U max(asteroids)O(n) 做法见「Python3 写法二」空间复杂度O(log U) 或 O(min(n, log U))。五、仓库源码对照两种解法与测试基建回到本仓库这道题的沉淀非常完整可以对照阅读解法实现leetcode/weekly/274/c/c.go 中同时保留了两个版本——asteroidsDestroyed1是排序模拟L10-L19asteroidsDestroyed是按二进制长度分组L21-L45后者使用了标准库math/bits的bits.Len计算二进制长度、slices.Max求最大值、math.MaxInt充当组内无元素的哨兵值与题解文档中的 Go 代码一一对应测试用例leetcode/weekly/274/c/c_test.go 内置两组官方样例mass10, asteroids[3,9,19,5,21]返回true10≥3→13≥5→18≥9→27≥19→46≥21mass5, asteroids[4,9,23,4]返回false5≥4→9≥4→13≥9→2223 卡死测试框架leetcode/testutil/leetcode.go 中的RunLeetCodeFuncWithExamples通过反射读取函数签名把 markdown 里的文本用例解析为真实参数并调用目标函数同时具备超时检测isTLE默认在调试模式下关闭与答案比对能力注释中还支持targetCaseNum指定只跑某一个用例、或-1指向最后一个用例后自动全量回归。测试文件头部的// Code generated by copypasta/template/leetcode/generator_test.go表明这类_test.go由仓库的测试生成器自动产出leetcode/weekly/274目录下 a/b/c/d 四题均为同一套「题目 md 解法 测试」结构。六、多语言位运算技巧速查两种解法的本质差异在于排序解法依赖全局比较而分组解法只依赖二进制长度这一位运算能力。各语言计算二进制长度的写法整理如下记元素为 x组号 i 二进制长度 − 1语言计算 x 的二进制长度获取最大值组内哨兵值Python3x.bit_length()max(asteroids)infGobits.Len(uint(x))slices.Max(asteroids)math.MaxIntJava32 - Integer.numberOfLeadingZeros(x)手写循环求mxInteger.MAX_VALUECbit_width(1u * x)ranges::max(asteroids)INT_MAXC31 - __builtin_clz(x)手写循环求mxINT_MAXJavaScript31 - Math.clz32(x)Math.max(...asteroids)InfinityRust31 - x.leading_zeros()asteroids.iter().max()i32::MAX使用要点组号 i 从 0 开始对应区间 [2ⁱ, 2ⁱ⁺¹)所以分组数组的长度只需取maxWidth 最大值二进制长度最后一组容纳 [2^(maxWidth-1), 2^maxWidth) 内的元素未出现的组以哨兵值标记inf/math.MaxInt/Integer.MAX_VALUE/INT_MAX/Infinity/i32::MAX遍历时跳过除 Python/JS 外累加质量一律用 64 位类型long/long long/int64 位平台 /i64C 版本还需在提前返回时手动free掉堆内存避免泄漏。七、总结这道题在贪心体系中的位置2126 的核心价值不在会做而在能证明。它演示了贪心算法两大经典论证工具从最小/最大开始贪心§1.1先处理门槛最低的对象是很多排序类贪心的共性——本题按质量从小到大处理与先满足最容易满足的需求是同构的思维交换论证法§1.7通过相邻逆序交换不破坏可行性证明贪心顺序不失最优性本题证法一就是冒泡式交换的标准示范证法二则展示了逆否命题 首失败点分界的补充视角。掌握这两把武器后遇到有序处理 累加收益形态的题目如吃糖果、合石块、安排会议等变体都能先写排序贪心再从容补证明。而本题的进阶做法还提供了一个额外的思维增量当问题只关心相对大小是否达标而不关心内部精确顺序时可以用数值范围压缩这里按二进制长度分桶替代排序——这种以桶代排的思想在值域较小的计数类问题中非常实用。原文档末尾还附有作者维护的贪心题单分类含从最小/最大开始贪心交换论证法等章节与按算法分类的刷题索引均为外链资源读者可沿 题解文档 末尾指引自行查阅仓库内则可通过 SOLUTIONS.md 所在目录结构 继续浏览其他周赛题解。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐codeforces-go 题解精读二进制数组全部变为 1 的最小反转次数——贪心唯一性与正确性证明LeetCode 双周赛 133 Bcodeforces go 题解精读二进制数组全部变为 1 的最小反转次数——贪心唯一性与正确性证明LeetCode 双周赛 133 B 导读 本题是 L科学计算LeetCode 双周赛 90 C 题 destroyTargets 全解同余分组 最小摧毁值算法codeforces-go 实战LeetCode 双周赛 90 C 题 destroyTargets 全解同余分组 最小摧毁值算法codeforces go 实战 本文以 leetc科学计算codeforces-go 题解专题LeetCode 1877「数组中最大数对和的最小值」——排序贪心与交换论证法证明codeforces go 题解专题LeetCode 1877「数组中最大数对和的最小值」——排序贪心与交换论证法证明 导读 本文围绕 LeetCode 第科学计算上一篇Claude Code 版本演进深度解读从 CHANGELOG 透视终端 AI 编程工具的迭代逻辑下一篇eslint-plugin-unicorn 的 prefer-array-flat-map 规则快照测试报告源码级解读与实战指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考