GESP认证C++编程真题解析 | B4452 [GESP202512 四级] 优先购买

​欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！

专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。

适合人群：

• 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
• 希望系统学习C++/Python编程的初学者
• 想要提升算法与编程能力的编程爱好者

附上汇总帖：GESP认证C++编程真题解析 | 汇总

【题目来源】

洛谷：[B4452 GESP202512 四级] 优先购买 - 洛谷

【题目描述】

小 A 有M MM元预算。商店有N NN个商品，每个商品有商品名S SS、价格P PP和优先级V VV三种属性，其中V VV为正整数，且V VV越小代表商品的优先级越高。

小 A 的购物策略为：

• 总是优先买优先级最高的东西；
• 如果有多个最高优先级商品，购买价格最低的；
• 如果有多个优先级最高且价格最低的商品，购买商品名字典序最小的。

小 A 想知道能购买哪些商品。

【输入】

第一行两个正整数M , N M, NM,N，代表预算和商品数。

之后N NN行，每行一个商品，依次为S i P i V i S_i\ P_i\ V_iSi​Pi​Vi​，代表第i ii个商品的商品名、价格、优先级。

数据保证不存在两个名字相同的商品。

【输出】

按照字典序从小到大的顺序，输出所有购买商品的商品名。

【输入样例】

20 4 apple 6 8 bus 15 1 cab 1 10 water 4 8

【输出样例】

bus cab water

【算法标签】

《洛谷 B4452 优先购买》 #排序# #GESP# #2025#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=1005;// 最大物品数量// 定义物品结构体structNode{string s;// 物品名称intp;// 物品价格intv;// 物品评分/价值};Node a[N];// 存储所有物品Node b[N];// 存储购买的物品intm,n;// m: 预算, n: 物品总数intcur;// 已购买物品数量// 第一个比较函数：用于初始排序// 排序优先级：v(评分)升序 → p(价格)升序 → s(名称)字典序boolcmp(Node x,Node y){if(x.v!=y.v)returnx.v<y.v;// 先按评分升序排序if(x.p!=y.p)returnx.p<y.p;// 评分相同，按价格升序returnx.s<y.s;// 评分和价格都相同，按名称字典序}// 第二个比较函数：按名称字典序排序boolcmp2(Node x,Node y){returnx.s<y.s;// 只按名称字典序排序}intmain(){// 输入预算m和物品数量ncin>>m>>n;// 输入n个物品的信息for(inti=1;i<=n;i++){cin>>a[i].s>>a[i].p>>a[i].v;}// 步骤1：对物品进行排序// 排序规则：先按v升序，v相同按p升序，都相同按s字典序sort(a+1,a+n+1,cmp);// 步骤2：在预算范围内尽可能多地购买物品for(inti=1;i<=n;i++){// 如果当前预算足够购买第i个物品if(m>=a[i].p){m-=a[i].p;// 扣除价格b[++cur]=a[i];// 将物品加入购买列表}// 这里不能break，因为后面可能有更便宜的物理可购买}// 步骤3：对购买的物品按名称字典序排序sort(b+1,b+cur+1,cmp2);// 步骤4：输出购买的物品名称for(inti=1;i<=cur;i++){cout<<b[i].s<<endl;}return0;}

【运行结果】

20 4 apple 6 8 bus 15 1 cab 1 10 water 4 8 bus cab water