科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载导读本文围绕 LeetCode 第 1833 题《雪糕的最大数量》Maximum Ice Cream Bars第 237 场周赛 B 题展开讲解其「按价格从低到高购买」的贪心思路、严谨的证明以及排序贪心与计数排序两种写法及其复杂度对比。同时结合当前仓库codeforces-go中的 题解源码 与 单元测试给出可直接运行、可验证的完整实现帮助你举一反三地掌握「从最小/最大开始贪心」这一类贪心题目的标准套路。一、题目回顾在预算内买最多的雪糕商店里有n根雪糕第i根雪糕的价格为costs[i]。你手上有coins枚硬币每根雪糕只能买一次目标是在总花费不超过coins的前提下买到尽可能多的雪糕并返回最大数量。这是一个非常典型的“资源有限、求数量最大化”的贪心问题要买的数量最多自然应当优先选择最便宜的商品把钱花在“刀刃”上。二、贪心思路与证明核心贪心策略按照价格从低到高购买一定可以得到最优解。原题解给出了严格的交换论证exchange argument式证明如果最优解没有按照价格从低到高购买那么把已买的某根较贵雪糕替换成没有买的更便宜雪糕我们买的雪糕数量不变仍然最优花的钱更少了没有超出预算。所以存在最优解是按照价格从低到高购买的。这个证明的关键点在于替换不改变数量用一根更便宜的雪糕换掉已买的一根更贵的雪糕买到的总根数保持不变替换不会超预算总花费只减不增因此依然满足总花费 ≤ coins反复替换可得标准形态只要存在一次“先买贵的、后或根本不买便宜的”的逆序就可以用上述替换消除它最终一定存在一个“按价格从小到大依次购买”的最优解。这一思路属于贪心题单中「§1.1 从最小/最大开始贪心」的典型例题当答案与“尽量用最小代价换取最大收益”相关时先排序、再顺序决策往往就是正确的贪心方向。三、写法一排序 贪心遍历先把costs从小到大排序然后依次购买。在遍历过程中维护剩余的钱coins若coins cost当前最便宜的剩余雪糕都买不起则直接返回已购数量i——即区间[0, i-1]的i根雪糕否则执行coins - cost继续购买下一根若循环结束仍未耗尽预算说明所有雪糕都能买下返回len(costs)。下面给出题解文档中全部七种语言的完整实现。class Solution: def maxIceCream(self, costs: List[int], coins: int) - int: costs.sort() # 按照价格从低到高买 for i, cost in enumerate(costs): if coins cost: # 钱不够 return i # 买 [0, i-1] 一共 i 根雪糕 coins - cost # 可以买所有雪糕 return len(costs)class Solution { public int maxIceCream(int[] costs, int coins) { Arrays.sort(costs); int n costs.length; // 按照价格从低到高买 for (int i 0; i n; i) { int cost costs[i]; if (coins cost) { // 钱不够 return i; // 买 [0, i-1] 一共 i 根雪糕 } coins - cost; } // 可以买所有雪糕 return n; } }class Solution { public: int maxIceCream(vectorint costs, int coins) { ranges::sort(costs); int n costs.size(); // 按照价格从低到高买 for (int i 0; i n; i) { int cost costs[i]; if (coins cost) { // 钱不够 return i; // 买 [0, i-1] 一共 i 根雪糕 } coins - cost; } // 可以买所有雪糕 return n; } };int cmp(const void* a, const void* b) { return *(int*)a - *(int*)b; } int maxIceCream(int* costs, int costsSize, int coins) { qsort(costs, costsSize, sizeof(int), cmp); // 按照价格从低到高买 for (int i 0; i costsSize; i) { int cost costs[i]; if (coins cost) { // 钱不够 return i; // 买 [0, i-1] 一共 i 根雪糕 } coins - cost; } // 可以买所有雪糕 return costsSize; }func maxIceCream(costs []int, coins int) int { slices.Sort(costs) // 按照价格从低到高买 for i, cost : range costs { if coins cost { // 钱不够 return i // 买 [0, i-1] 一共 i 根雪糕 } coins - cost } // 可以买所有雪糕 return len(costs) }var maxIceCream function(costs, coins) { costs.sort((a, b) a - b); const n costs.length; // 按照价格从低到高买 for (let i 0; i n; i) { const cost costs[i]; if (coins cost) { // 钱不够 return i; // 买 [0, i-1] 一共 i 根雪糕 } coins - cost; } // 可以买所有雪糕 return n; };impl Solution { pub fn max_ice_cream(mut costs: Veci32, mut coins: i32) - i32 { costs.sort_unstable(); // 按照价格从低到高买 for (i, cost) in costs.iter().enumerate() { if coins cost { // 钱不够 return i as _; // 买 [0, i-1] 一共 i 根雪糕 } coins - cost; } // 可以买所有雪糕 costs.len() as _ } }复杂度分析时间复杂度$\mathcal{O}(n\log n)$其中 $n$ 是 $\textit{costs}$ 的长度瓶颈在于排序空间复杂度$\mathcal{O}(1)$忽略排序过程本身的栈开销。四、写法二计数排序当价格取值域较小时例如 $U \max(\textit{costs})$ 不大可以放弃比较排序改用计数排序把时间复杂度优化到 $\mathcal{O}(n U)$求出最大价格mx开一个长度为mx1的计数数组cnt统计每个价格出现的次数从价格1到mx从小到大遍历若剩余钱连当前单价cost都买不起则直接break单价为cost的雪糕最多能买num min(cnt[cost], coins // cost)根花费cost * num并累加答案循环结束后返回ans。class Solution: def maxIceCream(self, costs: List[int], coins: int) - int: mx max(costs) cnt [0] * (mx 1) for cost in costs: cnt[cost] 1 # 按照价格从低到高买 ans 0 for cost in range(1, mx 1): if coins cost: # 钱不够 break num min(cnt[cost], coins // cost) coins - cost * num # 买 num 根雪糕 ans num return ansclass Solution { public int maxIceCream(int[] costs, int coins) { int mx 0; for (int cost : costs) { mx Math.max(mx, cost); } int[] cnt new int[mx 1]; for (int cost : costs) { cnt[cost]; } // 按照价格从低到高买 int ans 0; for (int cost 1; cost mx cost coins; cost) { int num Math.min(cnt[cost], coins / cost); coins - cost * num; // 买 num 根雪糕 ans num; } return ans; } }class Solution { public: int maxIceCream(vectorint costs, int coins) { int mx ranges::max(costs); vectorint cnt(mx 1); for (int cost : costs) { cnt[cost]; } // 按照价格从低到高买 int ans 0; for (int cost 1; cost mx cost coins; cost) { int num min(cnt[cost], coins / cost); coins - cost * num; // 买 num 根雪糕 ans num; } return ans; } };int maxIceCream(int* costs, int costsSize, int coins) { int mx 0; for (int i 0; i costsSize; i) { mx MAX(mx, costs[i]); } int* cnt calloc(mx 1, sizeof(int)); for (int i 0; i costsSize; i) { cnt[costs[i]]; } // 按照价格从低到高买 int ans 0; for (int cost 1; cost mx cost coins; cost) { int num MIN(cnt[cost], coins / cost); coins - cost * num; // 买 num 根雪糕 ans num; } free(cnt); return ans; }func maxIceCream(costs []int, coins int) (ans int) { mx : slices.Max(costs) cnt : make([]int, mx1) for _, cost : range costs { cnt[cost] } // 按照价格从低到高买 for cost : 1; cost mx cost coins; cost { num : min(cnt[cost], coins/cost) coins - cost * num // 买 num 根雪糕 ans num } return }var maxIceCream function(costs, coins) { const mx Math.max(...costs); const cnt Array(mx 1).fill(0); for (const cost of costs) { cnt[cost]; } // 按照价格从低到高买 let ans 0; for (let cost 1; cost mx cost coins; cost) { const num Math.min(cnt[cost], Math.floor(coins / cost)); coins - cost * num; // 买 num 根雪糕 ans num; } return ans; };impl Solution { pub fn max_ice_cream(costs: Veci32, mut coins: i32) - i32 { let mx *costs.iter().max().unwrap(); let mut cnt vec![0; mx as usize 1]; for cost in costs { cnt[cost as usize] 1; } // 按照价格从低到高买 let mut ans 0; for cost in 1..mx { if coins cost { // 钱不够 break; } let num cnt[cost as usize].min(coins / cost); coins - cost * num; // 买 num 根雪糕 ans num; } ans } }复杂度分析时间复杂度$\mathcal{O}(n U)$其中 $n$ 是 $\textit{costs}$ 的长度$U \max(\textit{costs})$空间复杂度$\mathcal{O}(U)$用于存储计数数组cnt。五、两种写法的取舍写法时间复杂度空间复杂度适用场景排序 贪心遍历$\mathcal{O}(n\log n)$$\mathcal{O}(1)$通用任何数据范围都可用代码最简洁计数排序$\mathcal{O}(n U)$$\mathcal{O}(U)$价格上界 $U$ 较小如 $10^4$ 以内时更快实践建议面试与竞赛中优先写「排序 贪心」它不依赖值域、不易出错当明确知道 $U$ 很小、需要追求线性时间时再使用计数排序写法。六、仓库中的实现与测试验证codeforces-go仓库将这道题收录在 leetcode/weekly/237/b 目录下包含三种文件b.go同时实现了两个版本的maxIceCream排序贪心版与maxIceCream2计数排序版源码与题解文档中的 Go 示例一一对应可直接复制运行b_test.go通过仓库自带的 LeetCode 测试框架验证正确性1833.md即本文所依据的题解笔记。测试用例解读测试文件 提供了三组官方示例输入 costs输入 coins期望输出说明[1,3,2,4,1]74依次购买 1、1、2、3共 4 根花费 7[10,6,8,7,7,8]50最便宜也要 6一根都买不起[1,6,3,1,2,5]206预算充足买下全部 6 根测试通过testutil.RunLeetCodeFuncWithExamples(t, maxIceCream, examples, targetCaseNum)驱动该框架定义在 leetcode/testutil/leetcode.go 中负责解析输入输出字符串、调用被测函数并比对结果targetCaseNum为-1时还可只运行最后一个用例用于本地调试。注意测试文件中的 TODO 注释“测试入参最小的情况”说明读者可自行补充边界用例例如costs为空、coins为 0 等进行验证。如何本地运行克隆仓库后在leetcode/weekly/237/b目录下执行go test -v即可看到三组用例的通过情况。若想只调试某一个用例可将b_test.go中的targetCaseNum改为对应用例编号例如1、2、3再运行。七、专题训练从最小/最大开始贪心本题是「从最小/最大开始贪心」这一类题目的入门代表其通用套路可以提炼为三步识别方向目标是“数量最多 / 代价最小”且每件物品代价独立优先选最小的排序后决策按代价从小到大排序顺序判断是否能承担必要时优化若值域小用计数排序或桶替代比较排序把 $\mathcal{O}(n\log n)$ 优化到 $\mathcal{O}(nU)$。在原题解的分类题单中本题被收录于贪心与思维题单的「§1.1 从最小/最大开始贪心」一节同题单还覆盖了基本贪心策略、反悔贪心、区间贪心、字典序贪心、数学与构造类贪心等进阶方向适合按题单循序渐进地刷题巩固。仓库中 贪心相关题解目录 也收录了大量周赛贪心题的实现与测试可与题单配合使用。总结LeetCode 1833 的精华在于先证明贪心正确交换论证再用排序落实决策最后视值域决定是否用计数排序优化。掌握这一从“证明 → 实现 → 优化”的完整链路你就能轻松迁移到同类“在预算内最大化数量”的问题上这也是竞赛题解中最值得反复揣摩的思维方式。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐LeetCode 1833「雪糕的最大数量」贪心排序题解背包误区、反证法证明与四语言实现LogicStack-LeetCode 刷穿系列LeetCode 1833「雪糕的最大数量」贪心排序题解背包误区、反证法证明与四语言实现LogicStack LeetCode 刷穿系列 本篇以「Logi教程文档LogicStack-LeetCode 题解1465. 切割后面积最大的蛋糕贪心 排序求二维最大面积LogicStack LeetCode 题解1465. 切割后面积最大的蛋糕贪心 排序求二维最大面积 本篇基于「宫水三叶的刷题日记」刷题仓库Logi教程文档Sails 框架下通过自定义 HTTP 中间件配置 P3P 隐私策略头P3P 兼容旧版 IE 应用实战指南Sails 框架下通过自定义 HTTP 中间件配置 P3P 隐私策略头P3P 兼容旧版 IE 应用实战指南 导读 本文讲解如何在 SailsNode.js科学计算创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考