题目描述
小杨的班级要举办一个环保手工作品展览，老师请小杨去文具店购买 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, 1。其中最便宜的价格是 1。对于种类 2：有两件商品，价格分别为 3, 10。其中最便宜的价格是 3。
计算总价：小杨购买这两类文具的总花费为 1+3=4。
数据范围
对于所有测试点，保证 1≤M≤N≤10^5，1≤Ki≤M，1≤Pi≤10^3。
题解：小杨的智慧购物
题目理解
本题的核心需求是为每一种文具找到它的最低售价，然后将所有种类的最低售价相加，得到买齐所有文具的总花费。题目中保证了每种文具至少有一件，无需考虑无货情况。数据范围 N 可达 10^5，要求解法的时间复杂度不能过高。
思路详解
本解题思路分为三个核心步骤，确保高效且准确地解决问题：
-
定义存储结构： 定义一个全局数组
mn，其中mn[i]专门用来存储第 i 种文具的最低价格。因为 C++ 全局数组默认初始值为 0，而题目中文具价格都是正整数，所以可以通过mn[k]==0来判断该种类文具是否还未读取过数据，这个判断条件既简洁又高效。 -
遍历更新最低价格： 通过第一个 for 循环遍历所有 n 件文具，对于每一件文具的种类 k 和价格 p，做两种情况处理：
- 若该种类是第一次读取（
mn[k]==0），直接将当前价格 p 赋值给mn[k]，作为该种类的初始最低价格； - 若该种类已经读取过数据，就使用
min函数比较当前存储的最低价格mn[k]和当前价格 p，保留较小值，这样能保证mn[k]始终存储该种类文具的最低价格。
- 若该种类是第一次读取（
-
累加计算总价： 通过第二个 for 循环遍历 1 到 m 的所有文具种类，将每种文具的最低价格
mn[i]逐一累加到ans中，最终ans就是买齐所有文具的总花费，最后输出ans即可完成解题。
#include<bits/stdc++.h>
using std;
n, m;
k, p;
mn[];
ans = ;
{
cin >> m >> n;
( i = ; i <= n; i++) {
cin >> k >> p;
(mn[k] == ) {
mn[k] = p;
} {
mn[k] = (mn[k], p);
}
}
( i = ; i <= m; i++) {
ans += mn[i];
}
cout << ans;
;
}
