CJTX01｜采购清单 题解

核心算法

排序贪心。

思路推导

将所有价格从小到大排序，选择前 $k$ 个价格并求和。

正确性说明

假设某个最优方案没有选择当前未选商品中的最低价格 $x$，却选择了价格更高的商品 $y$。用 $x$ 替换 $y$ 后，购买数量不变，总费用不会增加。因此一定存在一个最优方案包含所有应选的较低价格，最终就是排序后的前 $k$ 项。

复杂度

• 时间复杂度：$O(n\log n)$；
• 空间复杂度：$O(n)$（保存输入；排序本身通常只需 $O(\log n)$ 递归栈空间）。

易错点

• 题目要求恰好选择 $k$ 件，不能把所有商品都相加；
• 应按价格从小到大排序；
• 总费用必须使用 long long。