#3728. 文具采购
文具采购
题目描述
小明去文具店买笔。店里有 种笔,第 种笔每支价格 元,库存 支。小明有 元钱,他想买尽可能多的笔。
每种笔最多只能买库存数量,且可以只买其中一部分。请计算小明最多能买多少支笔。
输入格式
第一行两个整数 和 ,分别表示笔的种类数和总钱数。
接下来 行,每行两个整数 和 ,表示第 种笔的单价和库存数量。
输出格式
输出一个整数,表示最多能买的笔的数量。
样例
3 10
2 5
3 4
5 2
5
4 20
3 4
1 10
5 3
2 6
15
说明/提示
数据范围:,,,。
提示:为了买到最多的笔,应优先购买价格最低的笔。
解析
解题思路
小明希望用有限的钱买到尽可能多的笔。因为每支笔对“数量”的贡献都是 1,所以为了让总数量最大,应当优先购买价格最低的笔。这属于典型的贪心策略:按单价从小到大排序,依次尽量购买当前最便宜的笔,直到钱花完或库存买完。
算法选择理由
- 每种笔的库存有限,但可以只买一部分,因此问题等价于:在总花费不超过 m 的约束下,最大化购买总件数。
- 由于所有物品的“价值”相同(每件贡献 1),单位价格越低越划算,贪心选择价格最低的笔不会比任何其他方案差。
- 若存在更优方案,其中某支较贵的笔被购买,而较便宜的笔还有剩余库存未买,则用便宜笔替换贵笔可花更少钱买同样数量,矛盾。因此贪心正确。
算法步骤
- 读入 n、m 以及每种笔的单价 p_i 和库存 c_i。
- 将所有笔按单价升序排序。
- 依次遍历每种笔:
- 当前最多能买
min(c_i, m / p_i)支; - 累加数量,并从 m 中扣除相应花费;
- 若 m 已为 0 则提前结束。
- 当前最多能买
- 输出累计数量。
复杂度分析
- 时间复杂度:排序 O(n log n),遍历 O(n),总 O(n log n)。n ≤ 1000,完全满足 1 秒限制。
- 空间复杂度:存储 n 种笔的信息,O(n)。
注意使用 long long 保存答案和剩余钱数,防止中间计算溢出(尽管本题数据范围下 int 也足够,但更安全)。
来源
AI 生成 · 云端大模型(域):deepseek-chat · 普及- · 贪心