#3728. 文具采购

文具采购

题目描述

小明去文具店买笔。店里有 nn 种笔,第 ii 种笔每支价格 pip_i 元,库存 cic_i 支。小明有 mm 元钱,他想买尽可能多的笔。

每种笔最多只能买库存数量,且可以只买其中一部分。请计算小明最多能买多少支笔。

输入格式

第一行两个整数 nn 和 mm,分别表示笔的种类数和总钱数。

接下来 nn 行,每行两个整数 pip_i 和 cic_i,表示第 ii 种笔的单价和库存数量。

输出格式

输出一个整数,表示最多能买的笔的数量。

样例

3 10
2 5
3 4
5 2
5 
4 20
3 4
1 10
5 3
2 6
15 

说明/提示

数据范围:1≤n≤10001 \le n \le 1000,0≤m≤1060 \le m \le 10^6,1≤pi≤1041 \le p_i \le 10^4,0≤ci≤1040 \le c_i \le 10^4。

提示:为了买到最多的笔,应优先购买价格最低的笔。

解析

解题思路

小明希望用有限的钱买到尽可能多的笔。因为每支笔对“数量”的贡献都是 1,所以为了让总数量最大,应当优先购买价格最低的笔。这属于典型的贪心策略:按单价从小到大排序,依次尽量购买当前最便宜的笔,直到钱花完或库存买完。

算法选择理由

  • 每种笔的库存有限,但可以只买一部分,因此问题等价于:在总花费不超过 m 的约束下,最大化购买总件数。
  • 由于所有物品的“价值”相同(每件贡献 1),单位价格越低越划算,贪心选择价格最低的笔不会比任何其他方案差。
  • 若存在更优方案,其中某支较贵的笔被购买,而较便宜的笔还有剩余库存未买,则用便宜笔替换贵笔可花更少钱买同样数量,矛盾。因此贪心正确。

算法步骤

  1. 读入 n、m 以及每种笔的单价 p_i 和库存 c_i。
  2. 将所有笔按单价升序排序。
  3. 依次遍历每种笔:
    • 当前最多能买 min(c_i, m / p_i) 支;
    • 累加数量,并从 m 中扣除相应花费;
    • 若 m 已为 0 则提前结束。
  4. 输出累计数量。

复杂度分析

  • 时间复杂度:排序 O(n log n),遍历 O(n),总 O(n log n)。n ≤ 1000,完全满足 1 秒限制。
  • 空间复杂度:存储 n 种笔的信息,O(n)。

注意使用 long long 保存答案和剩余钱数,防止中间计算溢出(尽管本题数据范围下 int 也足够,但更安全)。

来源

AI 生成 · 云端大模型(域):deepseek-chat · 普及- · 贪心