有 M 种文具、共 N 件商品,每种只买最便宜的一件,求买齐 M 种的总花费。
老师请小杨去文具店购买 M 种不同的文具。商店里共有 N 件文具,每件文具都有一个种类编号(1 到 M)和价格。
小杨的预算有限,他想了一个聪明的办法:对于每种文具,他只买最便宜的那一件(如果同种文具有多件价格相同且都是最便宜的,他只会购买其中的一件)。请你帮小杨计算出,买齐这 M 种文具一共需要花费多少钱。
分组统计求最小值数组当桶累加求和
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 M、N;随后 N 行每行 K、P(种类编号、价格) |
| 输出 | 买齐 M 种文具的总花费 |
| 数据范围 | 1 ≤ M ≤ N ≤ 10⁵ |
| 种类编号 | 1 ≤ K ≤ M |
| 价格范围 | 1 ≤ P ≤ 1000 |
| 重要保证 | 每个种类至少有一件文具可买 |
best[K] 表示种类 K 的最低价格best[1..M] 累加样例数据:2 5,随后 5 行分别是 1 1、1 2、1 1、2 3、2 10。
best[1] = 1001,best[2] = 1001(足够大的哨兵值)
等待更新
1 < best[1] = 1001
best[1] 更新为 1
2 < best[1] = 1 不成立
忽略,best[1] 仍为 1
1 < 1 不成立(相等也不更新)
忽略,best[1] 仍为 1
3 < best[2] = 1001
best[2] 更新为 3
10 < 3 不成立
忽略,best[2] 仍为 3
best[1] + best[2] = 1 + 3
✅ 总价 = 4
| 种类 | 该种类的所有价格 | 最低价 | 是否买它 |
|---|---|---|---|
| 1 | 1、2、1 | 1 | ✅ 买 |
| 2 | 3、10 | 3 | ✅ 买 |
用 best[种类] 记录该种类的最低价,读入时实时更新
把所有商品按 (种类, 价格) 排序,每种取第一件
| N 的规模 | 桶数组 | 排序法 | 结论 |
|---|---|---|---|
| 1,000 | 约 1 千次 | 约 1 万次 | 都能过 |
| 100,000(本题上限) | 约 10 万次 | 约 170 万次 | 桶数组明显更省 |
第一行输入 M N,之后 N 行每行输入"种类编号 价格"。程序会分组求最低价并汇总。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; const int MAXP = 1001; // 价格上限 1000,用 1001 当"无穷大" int best[100005]; int main() { int M, N; scanf("%d %d", &M, &N); for (int i = 1; i <= M; i++) best[i] = MAXP; // 初始化为哨兵值 for (int i = 0; i < N; i++) { int k, p; scanf("%d %d", &k, &p); if (p < best[k]) best[k] = p; // 只保留每种的最低价 } int total = 0; for (int i = 1; i <= M; i++) total += best[i]; // 每种都必须买,直接加 printf("%d\n", total); return 0; }
| 代码 | 作用 | 为什么这样写 |
|---|---|---|
best[i] = MAXP | 初始化桶 | 保证第一次遇到任何价格都会更新 |
if (p < best[k]) best[k] = p; | 实时更新最低价 | 一遍扫描完成,不用保存所有商品 |
total += best[i] | 累加 | 题目保证每种至少一件,所以不会有哨兵值残留 |
写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
1 1 | 5 | 只有一种,只有一件 |
2 2 | 30 | 每种恰好一件 |
2 5 | 4 | 题面样例 |
3 4 | 18 | 种类乱序出现,仍要正确分桶 |
2 3 | 1999 | 价格取到上限 1000 |
p < best[k] 永远不成立,最低价永远是 0,答案也就错了。只用一个长度为 M + 1 的数组记录每种的最低价,不需要保存全部商品,所以空间是 O(M)。
✅ N = 10⁵ 时操作约 10 万次,瞬间完成。
// 桶统计通用套路:下标当"键",数组元素当"值" int best[100005]; // 求最小 int cnt[100005]; // 求次数 long long sum[100005]; // 求每类的和 for (int i = 1; i <= M; i++) best[i] = 1001; // 求最小要初始化成"无穷大" // 求次数则初始化为 0(全局数组默认就是 0) cnt[k]++; sum[k] += p;
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 数组当桶 | 用下标存种类编号 | 计数排序、桶排序、词频统计 |
| 哨兵初始化 | 设一个比所有合法值都"极值"的初值 | 求最小值、求最大值、DP 的边界 |
| 一遍扫描 | 边读边算,不保存原始数据 | 读入量很大但只需汇总的题目 |