CCF-GESP计算机学会等级考试2025年12月三级C++T2 小杨的智慧购物-平芜编程栈

B4450 [GESP202512 三级] 小杨的智慧购物

题目描述

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

商店里共有NNN件文具，每件文具都有一个种类编号（从111到MMM）和价格。

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

输入格式

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

之后NNN行，每行两个正整数KiK_iKi和PiP_iPi，分别代表第iii件文具的种类编号和它的价格。数据保证每个种类至少有一件文具可供购买。

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

说明/提示

样例解释

文具清单如下：

文具 1：种类 1，价格111
文具 2：种类 1，价格222
文具 3：种类 1，价格111
文具 4：种类 2，价格333
文具 5：种类 2，价格101010

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

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

数据范围

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

题解 B4450 小杨的智慧购物

题目理解

我首先分析这道题的核心需求：需要为每一种文具找到它的最低售价，然后将所有种类的最低售价相加，得到买齐所有文具的总花费。题目中保证了每种文具至少有一件，无需考虑无货情况，同时数据范围是1≤M≤N≤1051 \leq M \leq N \leq 10^51≤M≤N≤105，这要求解法的时间复杂度不能过高，我的代码能满足高效求解的要求。

思路详解

我的解题思路分为三个核心步骤，确保高效且准确地解决问题：

定义存储结构：
我定义了一个全局数组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>// 包含C++所有常用标准库，无需单独引入iostream、algorithm等头文件usingnamespacestd;intn,m;// 定义变量：n存储文具的总件数，m存储文具的种类数intk,p;// 定义临时变量：k存储当前读取的文具种类编号，p存储对应文具的价格intmn[100005];// mn[i]用于记录第i种文具的最低价格，数组大小100005适配题目中M<=1e5的最大范围intans=0;// 定义ans用于累加所有种类文具的最低价格总和，初始值为0intmain(){cin>>m>>n;// 从输入读取第一行的两个数：文具种类数m和文具总件数n// 循环n次，依次读取每一件文具的信息，并更新对应种类的最低价格for(inti=1;i<=n;i++){cin>>k>>p;// 读取第i件文具的种类k和价格p// 判断第k种文具的最低价格是否尚未初始化（全局数组默认初始值为0）if(mn[k]==0){mn[k]=p;// 若未初始化，直接将当前价格p设为该种类的初始最低价格}else{// 若已初始化，用min函数取当前最低价格和p的较小值，更新mn[k]mn[k]=min(mn[k],p);}}// 循环m次，累加1~m每种文具的最低价格，得到总花费for(inti=1;i<=m;i++){ans+=mn[i];}cout<<ans;// 输出最终计算得到的总花费return0;}

复杂度分析

时间复杂度：O(N+M)O(N+M)O(N+M)。读取N件文具的循环耗时O(N)O(N)O(N)，累加M种文具最低价格的循环耗时O(M)O(M)O(M)，对于10510^5105级别的数据能快速运行，不会超时。
空间复杂度：O(M)O(M)O(M)。主要消耗在存储最低价格的数组mn上，数组大小100005足以容纳题目中最大的M值，空间占用合理。

另一种思路

一、解题思路

我这道题的核心目标是统计每个文具种类的最低价格，再将所有种类的最低价求和。为了高效实现这个目标，我采用了「排序+遍历去重」的思路：

先对所有文具进行排序，排序规则是「先按种类升序，同种类按价格升序」。这样排序后，同种类的文具会集中在一起，且每个种类的第一个元素就是该种类的最低价。
遍历排序后的文具数组，只要当前文具的种类和前一个不一致，就说明这是一个新种类的最低价，将其价格累加到总价中即可（每个种类只会累加一次最低价）。

#include<bits/stdc++.h>usingnamespacestd;intn,m;// m：文具种类数，n：文具总数// 结构体存储每件文具的信息structnode{intk;// k：文具的种类编号intp;// p：文具的价格};node a[100005];// 数组存储所有n件文具，下标范围满足题目数据范围(≤10^5)intans=0;// 存储买齐所有种类文具的总价，初始化为0// 自定义排序比较函数，用于对文具数组进行排序boolcmp(node x,node y){// 优先规则1：按文具种类升序排列，保证同种类文具相邻if(x.k==y.k)// 优先规则2：同种类文具按价格升序排列，保证最便宜的在该种类最前面returnx.p<y.p;returnx.k<y.k;}intmain(){// 输入文具种类数m和文具总数ncin>>m>>n;// 循环输入n件文具的种类和价格，存入数组a（数组从1开始索引）for(inti=1;i<=n;i++){cin>>a[i].k>>a[i].p;}// 对数组a的[1, n]区间元素进行排序，使用自定义cmp规则sort(a+1,a+n+1,cmp);// 遍历排序后的数组，累加每个种类的最低价格for(inti=1;i<=n;i++){// 若当前文具种类与前一个不同，说明是该种类的第一个元素（即最低价）if(a[i].k!=a[i-1].k){ans+=a[i].p;// 累加该种类的最低价到总价}}// 输出最终总价cout<<ans;return0;}

二、代码各部分说明

结构体与数组：我定义了node结构体来存储每件文具的种类k和价格p，并用大小为100005的数组a存储所有文具，满足题目中n≤10^5的数据范围。
自定义排序函数cmp：这是实现思路的关键。先按种类k升序排列，保证同种类文具相邻；同种类时按价格p升序排列，保证该种类最低价排在最前面，为后续遍历累加提供便利。
输入数据：先读取种类数m和总数n，再循环n次读取每件文具的信息，存入数组a中（我习惯数组从1开始索引，方便后续判断前一个元素）。
排序处理：使用sort函数对数组a的[1, n]区间排序，传入自定义的cmp函数作为排序规则，完成前文提到的排序要求。
累加总价：遍历排序后的数组，通过a[i].k != a[i-1].k判断当前元素是否是新种类的第一个元素（即最低价）。若是，则将其价格累加到ans中。由于数组从1开始，a[0]是默认值（与a[1]种类必然不同），因此第一个种类的最低价会被正常累加。
输出结果：最后输出累加后的总价ans，即为题目要求的答案。