题目描述
小杨的班级要举办一个环保手工作品展览，老师请小杨去文具店购买 M 种不同的文具（例如：铅笔、橡皮、尺子等）。
商店里共有 N 件文具，每件文具都有一个种类编号（从 1 到 M）和价格。
小杨的预算有限，他的做法很直接：每种文具只买最便宜的那一件；如果同一种文具有多件价格相同且都最便宜，他也只拿其中一件。请你算出，买齐这 M 种文具一共要花多少钱。
输入格式
第一行两个正整数 M,N，代表文具的种类数和总数。
之后 N 行，每行两个正整数 Ki 和 Pi，分别代表第 i 件文具的种类编号和它的价格。数据保证每个种类至少有一件文具可供购买。
输出格式
输出一行，代表购买文具的总价。
输入输出样例 #1
输入 #1
2 5
1 1
1 2
1 1
2 3
2 10
输出 #1
4
说明/提示
样例解释
文具清单如下：
- 文具 1：种类 1，价格 1
- 文具 2：种类 1，价格 2
- 文具 3：种类 1，价格 1
- 文具 4：种类 2，价格 3
- 文具 5：种类 2，价格 10
小杨的选择很简单：种类 1 里最便宜的是 1，种类 2 里最便宜的是 3。总价就是 1+3=4。
数据范围
对于所有测试点，保证 1≤M≤N≤10^5，1≤Ki≤M，1≤Pi≤10^3。
题解：按种类取最小值
这题其实就是统计每个种类的最低价格，然后把这些最低价加起来。题目保证每个种类都至少出现一次，所以不用处理'某类没货'的情况。数据规模到 10^5，做法得老实一点，不能靠暴力扫多轮。
思路一：直接维护每类最小值
我更倾向于这种写法，简单，也不容易出错。
读入每一件文具时，直接更新它所属种类的最低价。因为价格都是正整数，可以用一个数组 mn 记录每类当前最小值。mn[k] 还没被赋值时为 0，第一次见到这个种类就直接写入，后面再拿 min 比一下即可。
最后再把 1..M 这些种类的最小价加起来，答案就出来了。
#include<bits/stdc++.h>
using namespace std;
int n, m; // n：文具总数，m：文具种类数
int k, p; // k：种类编号，p：价格
int mn[100005]; // mn[i] 记录第 i 种文具的最低价格
int ans = 0; // 总价
int main() {
cin >> m >> n;
for (int i = 1; i <= n; i++) {
cin >> k >> p;
if (mn[k] == 0) {
mn[k] = p;
} else {
mn[k] = min(mn[k], p);
}
}
for (int i = 1; i <= m; i++) {
ans += mn[i];
}
cout << ans;
return 0;
}
思路二：排序后取每类第一个
如果你更习惯先把数据整理好，再做统计，也可以用排序。
把所有文具按'种类升序、价格升序'排序。这样同一种类会挨在一起，而且排在最前面的就是这个种类的最低价。遍历排序后的数组，只要当前元素的种类和前一个不同，就说明碰到了一个新种类，把它的价格加进答案里就行。
这套写法也能过，不过我会更偏向上面的数组做法，因为它不需要排序，读一遍就结束，思路更短。
#include<bits/stdc++.h>
using namespace std;
int n, m;
struct node {
int k;
int p;
};
node a[100005];
int ans = 0;
bool cmp(node x, node y) {
if (x.k == y.k) {
return x.p < y.p;
}
return x.k < y.k;
}
int main() {
cin >> m >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i].k >> a[i].p;
}
sort(a + 1, a + n + 1, cmp);
for (int i = 1; i <= n; i++) {
if (a[i].k != a[i - 1].k) {
ans += a[i].p;
}
}
cout << ans;
return 0;
}
复杂度分析
- 方法一：时间复杂度 O(N+M)，空间复杂度 O(M)
- 方法二：时间复杂度 O(N log N)，空间复杂度 O(N)
题目数据不大，两种都能稳稳通过。实际做题时，直接维护最小值通常更省事，也更不容易写错。
