A21138. 小杨的智慧购物小杨的班级要举办一个环保⼿⼯作品展览，⽼师请小杨去⽂具店购买M种不同的⽂具（例如：铅笔、橡⽪、尺⼦等）。商店⾥共有N件⽂具，每件⽂具都有一个种类编号（1到M）和价格。小杨的预算有限，他想了一个聪明的办法：对于每种⽂具，他只买最便宜的那一件（如果同种⽂具有多件价格相同且都是最便宜的，他只会购买其中的一件）。请你帮小杨计算出，买齐这M种⽂具一共需要花费多少钱。
填空题
中等
知识点
题目描述
小杨的智慧购物
小杨的班级要举办一个环保⼿⼯作品展览，⽼师请小杨去⽂具店购买M种不同的⽂具（例如：铅笔、橡⽪、尺⼦等）。
商店⾥共有N件⽂具，每件⽂具都有一个种类编号（1到M）和价格。
小杨的预算有限，他想了一个聪明的办法：对于每种⽂具，他只买最便宜的那一件（如果同种⽂具有多件价格相同且都是最便宜的，他只会购买其中的一件）。请你帮小杨计算出，买齐这M种⽂具一共需要花费多少钱。
输入格式
第一行两个正整数M,N，代表⽂具的种类数和总数。
之后N行，每行两个正整数 Ki 和 Pi ，分别代表第 i 件⽂具的种类编号和它的价格。数据保证每个种类⾄少有一件⽂具可供购买。
输出格式
输出一行，代表购买⽂具的总价。
样例
输入样例
2 5
1 1
1 2
1 1
2 3
2 10输出样例
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 <cstring>
using namespace std;
int min_price[10005]
int main() {
int M, N;
cin >> M >> N;
int min_price[100005];
for (int i = 0; i <= M; i++)
min_price[i] = 100000000;
for (int i = 0; i < N; ++i) {
int K, P;
cin >> K >> P;
min_price[K] = min(min_price[K], P);
}
int total_cost = 0;
for (int k = 1; k <= M; ++k) {
total_cost += min_price[k];
}
cout << total_cost;
return 0;
}
上一题
下一题