CCF-GESP计算机学会等级考试2025年12月四级C++T2 优先购买

B4452 [GESP202512 四级] 优先购买

题目描述

小 A 有MMM元预算。商店有NNN个商品，每个商品有商品名SSS、价格PPP和优先级VVV三种属性，其中VVV为正整数，且VVV越小代表商品的优先级越高。

小 A 的购物策略为：

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

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

输入格式

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

之后NNN行，每行一个商品，依次为Si Pi ViS_i\ P_i\ V_iSi​Pi​Vi​，代表第iii个商品的商品名、价格、优先级。

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

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

bus cab water

说明/提示

数据范围

对于所有测试点，保证1≤∣Si∣≤101 \leq |S_i| \leq 101≤∣Si​∣≤10，1≤M,Pi≤1051 \leq M, P_i \leq 10^51≤M,Pi​≤105，1≤N≤1031 \leq N \leq 10^31≤N≤103，1≤Vi≤101 \leq V_i \leq 101≤Vi​≤10。商品名仅由小写字母组成且不存在两个相同的商品名。

题解：优先购买

解题思路

我解决这道题的核心思路是**“先按规则排序商品，再按优先级依次购买，最后整理输出结果”**，整体分为三个关键步骤：

1. 数据封装：使用结构体统一存储每个商品的名称、价格、优先级，方便后续排序和遍历；
2. 自定义排序：严格遵循题目要求的三层优先级（优先级v→价格p→名字典序），对所有商品进行排序，确保靠前的商品是当前最该购买的；
3. 模拟购买与结果整理：遍历排序后的商品，预算足够则购买并记录商品名，最后将购买列表按字典序排序后输出，满足题目输出要求。

#include<bits/stdc++.h>// 包含所有常用标准库头文件，简化编程流程usingnamespacestd;// 使用std命名空间，避免重复书写std::前缀intm,n;// 定义全局变量：m存储初始预算，n存储商品总数structnode{// 定义结构体node，用于封装单个商品的所有属性string s;// 商品名称intp;// 商品价格intv;// 商品优先级（v越小优先级越高）};node a[1005];// 定义结构体数组，存储所有商品（大小1005满足n≤1000的要求）vector<string>name;// 定义字符串向量，存储最终成功购买的商品名// 自定义排序函数cmp，严格按照题目要求的优先级规则排序boolcmp(node x,node y){// 第一关键字：优先级v，v越小越靠前（优先购买高优先级商品）if(x.v!=y.v)returnx.v<y.v;// 第二关键字：价格p，优先级相同时，价格越低越靠前if(x.p!=y.p)returnx.p<y.p;// 第三关键字：商品名字典序，优先级和价格都相同时，字典序越小越靠前returnx.s<y.s;}intmain(){cin>>m>>n;// 输入初始预算m和商品数量n// 循环n次，输入每个商品的名称、价格、优先级，存入结构体数组afor(inti=1;i<=n;i++){cin>>a[i].s>>a[i].p>>a[i].v;}// 对结构体数组a进行排序（从第1个到第n个元素），排序规则为自定义的cmp函数sort(a+1,a+n+1,cmp);// 遍历排序后的商品，按照优先级顺序尝试购买for(inti=1;i<=n;i++){// 如果当前商品价格≤剩余预算，说明可以购买if(a[i].p<=m){name.push_back(a[i].s);// 将该商品名加入购买列表m-=a[i].p;// 剩余预算减去当前商品价格，更新预算}}// 题目要求输出时按商品名字典序从小到大排列，因此对购买列表排序sort(name.begin(),name.end());// 循环遍历购买列表，逐行输出每个商品名for(inti=0;i<name.size();i++){cout<<name[i]<<"\n";}return0;// 程序正常结束}

代码分步解析

1. 数据结构定义

   • 我用struct node封装了商品的三个属性，避免零散变量管理的混乱；
   • 结构体数组a[1005]用于存储所有商品，vector<string> name用于动态记录购买的商品名，灵活且方便后续排序。

2. 自定义排序函数（核心）
   这是实现题目购买策略的关键，我按题目要求分层定义排序规则：

   • 第一层：优先级v从小到大（x.v < y.v），保证优先购买优先级最高的商品；
   • 第二层：价格p从小到大（x.p < y.p），保证优先级相同时购买最低价商品；
   • 第三层：商品名字典序从小到大（x.s < y.s），保证前两个条件相同时购买字典序最小的商品。

3. 主函数逻辑

   • 输入数据：先读取预算m和商品数n，再循环读取每个商品的信息存入结构体数组；
   • 商品排序：使用C++标准库sort函数，结合自定义cmp函数，完成商品优先级排序；
   • 模拟购买：遍历排序后的商品，判断预算是否足够，足够则购买并更新预算，同时记录商品名；
   • 结果整理与输出：由于题目要求输出按字典序排列，因此先对购买列表排序，再逐行输出。