2025年12月GESP(C++三级): 小杨的智慧购物-平芜编程栈

2025年12月GESP(C++三级): 小杨的智慧购物

题目描述

小杨的班级要举办一个环保手工作品展览，老师请小杨去文具店购买M MM种不同的文具（例如：铅笔、橡皮、尺子等）。

商店里共有N NN件文具，每件文具都有一个种类编号（从1 11到M MM）和价格。

小杨的预算有限，他想了一个聪明的办法：对于每种文具，他只买最便宜的那一件（如果同种文具有多件价格相同且都是最便宜的，他只会购买其中的一件）。请你帮小杨计算出，买齐这M MM种文具一共需要花费多少钱。

输入格式

第一行两个正整数M , N M, NM,N，代表文具的种类数和总数。

之后N NN行，每行两个正整数K i K_iKi和P i P_iPi，分别代表第i ii件文具的种类编号和它的价格。数据保证每个种类至少有一件文具可供购买。

输出格式

输出一行，代表购买文具的总价。

输入输出样例 1

输入 1

2 5 1 1 1 2 1 1 2 3 2 10

输出 1

说明/提示

样例解释

文具清单如下：

文具 1：种类 1，价格1 11
文具 2：种类 1，价格2 22
文具 3：种类 1，价格1 11
文具 4：种类 2，价格3 33
文具 5：种类 2，价格10 1010

小杨的选择过程：对于种类 1：有三件商品，价格分别为1 , 2 , 1 1, 2, 11,2,1。其中最便宜的价格是1 11。对于种类 2：有两件商品，价格分别为3 , 10 3, 103,10。其中最便宜的价格是3 33。

计算总价：小杨购买这两类文具的总花费为1 + 3 = 4 1 + 3 = 41+3=4。

数据范围

对于所有测试点，保证1 ≤ M ≤ N ≤ 10 5 1 \leq M \leq N \leq 10^51≤M≤N≤105，1 ≤ K i ≤ M 1 \leq K_i \leq M1≤Ki≤M，1 ≤ P i ≤ 10 3 1 \leq P_i \leq 10^31≤Pi≤103。

题目分析

问题理解

小杨需要购买M种不同的文具，每种文具只购买最便宜的一件。给定N件文具的信息（种类编号和价格），要求计算购买所有M种文具的最小总花费。

算法思路

核心思想：为每种文具维护一个最低价格，最后将所有种类的最低价求和。
具体实现：
- 使用数组c[i]记录第i种文具的最低价格，初始化为一个足够大的数（因为题目中价格最大为1000，所以初始化为1001）。
- 遍历所有文具，对于每件文具，如果它的价格低于当前记录的同种类最低价，就更新最低价。
- 最后累加所有种类的最低价格。

复杂度分析

时间复杂度：O(N)，只需要遍历一次所有文具。
空间复杂度：O(M)，使用一个大小为M+1的数组存储每种文具的最低价格。

代码实现

#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+10;// 定义最大数据范围intm,n,c[N];// m:种类数, n:文具总数, c[i]:第i种文具的最低价格intmain(){// 输入文具种类数和文具总数cin>>m>>n;// 初始化每种文具的最低价格为1001（因为题目中价格最大为1000）for(inti=1;i<=m;i++){c[i]=1001;// 1001作为初始值，比任何实际价格都大}// 遍历每件文具for(inti=1;i<=n;i++){intk,p;cin>>k>>p;// 输入种类编号和价格c[k]=min(c[k],p);// 更新该种类的最低价格}// 计算总花费：将所有种类的最低价格相加intsum=0;for(inti=1;i<=m;i++){sum+=c[i];}// 输出结果cout<<sum;return0;}

功能分析

1.输入处理：

读取文具种类数M和文具总数N
逐件读取文具的种类和价格

2.核心逻辑：

为每种文具维护最低价格
使用min()函数更新最低价
初始值1001确保能被任何实际价格更新

3.输出结果：

累加所有种类的最低价格
输出总花费

4.示例验证

对于样例输入：

2 5 1 1 1 2 1 1 2 3 2 10

程序执行过程：

初始化c[1]=1001, c[2]=1001
读入(1,1)：c[1]=min(1001,1)=1
读入(1,2)：c[1]=min(1,2)=1
读入(1,1)：c[1]=min(1,1)=1
读入(2,3)：c[2]=min(1001,3)=3
读入(2,10)：c[2]=min(3,10)=3
总花费：1+3=4

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

一、CSP信奥赛C++通关学习视频课：
- C++语法基础
- C++语法进阶
- C++算法
- C++数据结构
- CSP信奥赛数学
- CSP信奥赛STL
二、CSP信奥赛C++竞赛拿奖视频课：
- 信奥赛csp-j初赛高频考点解析
- CSP信奥赛C++复赛集训课（12大高频考点专题集训）
三、考级、竞赛刷题题单及题解：
- GESP C++考级真题题解
- CSP信奥赛C++初赛及复赛高频考点真题解析
- CSP信奥赛C++一等奖通关刷题题单及题解

详细内容：

1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

2、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

3、csp信奥赛冲刺一等奖有效刷题题解：

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

2025 csp-j 复赛真题及答案解析（最新更新）
2025 csp-x(山东) 复赛真题及答案解析（最新更新）
2025 csp-x(河南) 复赛真题及答案解析（最新更新）
2025 csp-x(辽宁) 复赛真题及答案解析（最新更新）
2025 csp-x(江西) 复赛真题及答案解析（最新更新）
2025 csp-x(广西) 复赛真题及答案解析（最新更新）
2020 ~ 2024 csp 复赛真题题单及题解
2019 ~ 2022 csp-j 初赛高频考点真题分类解析
2021 ~ 2024 csp-s 初赛高频考点解析
2023 ~ 2024 csp-x (山东)初赛真题及答案解析
2024 csp-j 初赛真题及答案解析
2025 csp-j 初赛真题及答案解析（最新更新）
2025 csp-s 初赛真题及答案解析（最新更新）
2025 csp-x (山东)初赛真题及答案解析(最新更新)
2025 csp-x (江西)初赛真题及答案解析(最新更新)
2025 csp-x (辽宁)初赛真题及答案解析(最新更新)

CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

129 道刷题练习和详细题解，涉及：模拟算法、数学思维、二分算法、前缀和、差分、深搜、广搜、DP专题、树和图

4、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}

2025年12月GESP(C++三级): 小杨的智慧购物