科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载本篇题解围绕力扣双周赛 145Biweekly Contest 145第 1 题「Minimum Operations to Make Array Values Equal to K」展开完整讲解该题在 codeforces-go 仓库中的解法思路、分类讨论、多语言代码实现与测试验证方式。读完本篇你将掌握选取合法 h 后只需关注最大值与次大值这一关键观察以及答案等于不同元素个数视 k 与最小值关系减一这一可直接套用的贪心结论并能据此在 LeetCode 原题页面 上独立 AC 同类题型。本文对应仓库源码题解文档、Go 实现、测试数据、测试代码。题目背景与所属场次本题来自力扣双周赛 145Biweekly Contest 145的第 1 题原题名为「Minimum Operations to Make Array Values Equal to K」。仓库中该场次题解索引见 leetcode/biweekly/145/README.md共包含 Q1–Q4 四道题Q2 为排列回溯、Q3 为 Dijkstra 最短路、Q4 为枚举 GCD 并查集其中 Q1 即为本文主角官方题解标题的核心思想是「本质是计算不同元素个数」。思考框架三问定解法原文档leetcode/biweekly/145/a/README.md给出了清晰的思考框架是解出此题的关键路径理解操作在做什么——先搞清楚一次操作到底能改变数组中的哪些数把 nums 中的数都变成一样的能变成哪些数——确定操作可达的目标集合如何最小化操作次数——在可达目标中选出最优的 k并统计所需步数。这三问层层递进第一问锁定了操作的作用范围第二问给出了可达目标的理论边界第三问则在边界内贪心取最优。下面逐一展开。操作在做什么为什么只能动最大值题目说「选择一个整数 h」但并非任意 h 都合法。根据题目对「合法」的定义h 不能低于 nums 的次大值。原文档以 $\textit{nums}[5,2,5,4,5]$ 为例说明该数组最大值是 $5$次大值是 $4$若 $h4$比如 $h3$则数组中大于 $h$ 的数$5$ 和 $4$并不全部相等违反合法性的约束因此合法操作只能选择 $h\ge 4$此时大于 $h$ 的数只可能是最大值 $5$操作只会把最大值改写成 $h$。由此得到核心结论一次操作只能改变大于次大值的数也就是当前的最大值而次大值保持不变。换句话说操作过程是最大值被逐级压到次大值的过程。能变成哪些数可达目标的理论边界既然每次操作只能把当前最大值压到次大值那么数组最终能统一成什么值继续用 $\textit{nums}[5,2,5,4,5]$ 推演选择 $h4$当前次大值把最大值 $5$ 改成 $4$得到 $[4,2,4,4,4]$此时原次大值 $4$ 升级为最大值选择 $h2$当前次大值把最大值 $4$ 改成 $2$得到 $[2,2,2,2,2]$所有数相同若想继续改成比 $2$ 更小的值比如 $0$只需选择 $h0$数组变为 $[0,0,0,0,0]$。因此原文档得出关键结论nums 中的数可以都变成任意 $\le \min(\textit{nums})$ 的数。注意这里 $k$ 必须不大于数组最小值——这是第二问与第三问衔接的桥梁也是判题时返回 $-1$ 的条件来源。最小化操作次数分类讨论与贪心为了最小化操作次数每次选择 $h$ 为当前次大值是最优的——贪心直觉是能一步到达次大值没必要分好几步走。基于此原文档给出三分类讨论若 $k \min(nums)$目标值大于数组最小值不可达返回 $-1$若 $k \min(nums)$操作次数为nums 中不同元素个数减一。示例 $[5,2,5,4,5]$ 中最大值 $5\to 4\to 2$ 共 $2$ 次操作正好等于不同元素 ${2,4,5}$ 的个数 $3$ 减一若 $k \min(nums)$操作次数为nums 中不同元素个数因为都变成 $\min(nums)$ 后还需要额外一次操作才能都变成 $k$。这三个分支合起来可以统一成一个公式设 $\textit{distinct}$ 为不同元素个数$$\text{answer} \textit{distinct} - (k \min(nums) ? 1 : 0)$$其中 $k\min(nums)$ 时返回 $-1$ 的判据必须最先执行。多语言代码实现原文档给出 Python、Java、C、Go、JavaScript、Rust 六种语言的实现核心都是取最小值、判不可达、统计不同元素个数。这里完整呈现如下。Pythonclass Solution: def minOperations(self, nums: List[int], k: int) - int: mn min(nums) if k mn: return -1 return len(set(nums)) - (k mn)Javaclass Solution { public int minOperations(int[] nums, int k) { int min Arrays.stream(nums).min().getAsInt(); if (k min) { return -1; } int distinctCount (int) Arrays.stream(nums).distinct().count(); return distinctCount - (k min ? 1 : 0); } }Cclass Solution { public: int minOperations(vectorint nums, int k) { int mn ranges::min(nums); if (k mn) { return -1; } unordered_setint st(nums.begin(), nums.end()); return st.size() - (k mn); } };Go与仓库 leetcode/biweekly/145/a/a.go 完全一致func minOperations(nums []int, k int) int { mn : slices.Min(nums) if k mn { return -1 } set : map[int]struct{}{} for _, x : range nums { set[x] struct{}{} } if k mn { return len(set) - 1 } return len(set) }JavaScriptvar minOperations function(nums, k) { const min Math.min(...nums); if (k min) { return -1; } return new Set(nums).size - (k min ? 1 : 0); };Rustuse std::collections::HashSet; impl Solution { pub fn min_operations(nums: Veci32, k: i32) - i32 { let min *nums.iter().min().unwrap(); if k min { return -1; } let set nums.into_iter().collect::HashSet_(); set.len() as i32 - if k min { 1 } else { 0 } } }复杂度分析原文档给出的复杂度结论为时间复杂度$\mathcal{O}(n)$其中 $n$ 是 $\textit{nums}$ 的长度——求最小值与统计不同元素个数均为线性扫描空间复杂度$\mathcal{O}(n)$——需要用哈希集合记录不同元素。这与实现完全吻合无论哪种语言都只有遍历一次求最小值与遍历一次去重两趟线性操作。仓库源码级验证从题解到可运行测试本题的解法不仅停留在题解文档中仓库还提供了完整的 Go 实现与数据驱动测试构成题解 → 实现 → 测试的完整闭环。Go 实现leetcode/biweekly/145/a/a.go与题解文档中 sol-Go 的代码一致先用slices.Min求出最小值 $mn$$kmn$ 直接返回 $-1$再用map[int]struct{}统计不同元素个数最后按 $k$ 与 $mn$ 的关系返回len(set)-1或len(set)。这里使用空结构体struct{}{}作为集合元素是 Go 中节省内存的标准写法。测试用例leetcode/biweekly/145/a/a.txt以输入 期望输出逐行排列覆盖了三种典型场景[5,2,5,4,5] 2 2 [2,1,2] 2 -1 [9,7,5,3] 1 4用例 1[5,2,5,4,5], k2不同元素为 ${2,4,5}$$k\min2$答案 $3-12$用例 2[2,1,2], k2 \min1$不可达答案 $-1$用例 3[9,7,5,3], k1 \min3不同元素为 $4$ 个答案 $4$。测试驱动leetcode/biweekly/145/a/a_test.go通过testutil.RunLeetCodeFuncWithFile(t, minOperations, a.txt, 0)调用仓库的 LeetCode 测试工具实现在 leetcode/testutil/leetcode.go读取文本用例并逐条断言。该工具会按函数的入参个数与返回值个数把每 $n$ 行解析为一组测试数据RunLeetCodeFuncWithFile中的fNumIn fNumOut逻辑并支持targetCaseNum指定跑单个用例如-1表示最后一个自动化验证算法正确性。这个文本用例 数据驱动测试的框架在整个仓库的 LeetCode 题解中通用方便读者本地运行go test复现结果。小结一句话记住本题回到原文档的思考框架本题的解题链条可以浓缩为合法操作只能改动最大值 → 所有数可统一成任意不超过最小值的数 → 若 $k$ 不可达返回 $-1$否则答案等于不同元素个数减去$k$ 恰为最小值时的 1。掌握化归到不同元素个数这一思维不仅在本题能快速 AC对同类通过特定操作统一数组元素的构造/贪心题目也有直接借鉴价值。若想按知识点系统刷题可参考仓库题解文档末尾的分类题单滑动窗口、二分、单调栈、图论、动态规划等十二大类将本题归入「贪心与思维」类目继续巩固。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐循环数组周期归约 中位数贪心makeSubKSumEqual 最小操作次数题解codeforces-go 仓库 LeetCode 双周赛 101 C 题深度解析循环数组周期归约 中位数贪心makeSubKSumEqual 最小操作次数题解codeforces go 仓库 LeetCode 双周赛 101 C 题科学计算codeforces-go 仓库实战解析用栈一行思路解 LeetCode 双周赛 132 第 1 题 Clear Digitscodeforces go 仓库实战解析用栈一行思路解 LeetCode 双周赛 132 第 1 题 Clear Digits 本篇文章以 codeforce科学计算codeforces-go 仓库中的 LeetCode 3160 双哈希表解法球的颜色不同颜色数双周赛 131 第 3 题codeforces go 仓库中的 LeetCode 3160 双哈希表解法球的颜色不同颜色数双周赛 131 第 3 题 本篇技术指南围绕 codefo科学计算上一篇OpenCore黑苹果自动化配置终极指南从零到精通完整教程下一篇Longhorn 定时任务 Age-Based 保留策略基于时长的快照/备份/系统备份自动清理创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考