《B4450 [GESP202512 三级] 小杨的智慧购物》
题目背景
对应的选择、判断题：https://ti.luogu.com.cn/problemset/1199
题目描述
小杨的班级要举办一个环保手工作品展览，老师请小杨去文具店购买 M 种不同的文具（例如：铅笔、橡皮、尺子等）。
商店里共有 N 件文具，每件文具都有一个种类编号（从 1 到 M）和价格。
小杨的预算有限，他想了一个聪明的办法：对于每种文具，他只买最便宜的那一件（如果同种文具有多件价格相同且都是最便宜的，他只会购买其中的一件）。请你帮小杨计算出，买齐这 M 种文具一共需要花费多少钱。
输入格式
第一行两个正整数 M,N，代表文具的种类数和总数。
之后 N 行，每行两个正整数 Ki 和 Pi，分别代表第 i 件文具的种类编号和它的价格。数据保证每个种类至少有一件文具可供购买。
输出格式
输出一行，代表购买文具的总价。
输入输出样例
输入 #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≤105，1≤Ki≤M，1≤Pi≤103。
代码实现：
#include <iostream> #include <vector> #include <climits> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int M, N; cin >> M >> N; vector<int> min_price(M + 1, INT_MAX); for (int i = 0; i < N; ++i) { int K, P; cin >> K >> P; if (P < min_price[K]) { min_price[K] = P; } } long long sum = 0; for (int i = 1; i <= M; ++i) { sum += min_price[i]; } cout << sum << endl; return 0; }