2025年12月GESP(C++四级): 优先购买

2025年12月GESP(C++四级): 优先购买

题目描述

小 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个商品的商品名、价格、优先级。

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

输出格式

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

输入输出样例 1

输入 1

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

输出 1

bus cab water

数据范围

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

思路分析

本题要求按照特定优先级顺序购买商品，并在预算允许范围内尽可能多地购买商品。解题思路如下：

1. 购买策略排序：根据题目要求，需要先按优先级V（越小越优先）、再按价格P（越低越优先）、最后按商品名S（字典序越小越优先）排序
2. 贪心购买：按照上述排序顺序依次尝试购买，只要预算足够就购买该商品
3. 输出要求：最终需要按商品名字典序输出购买的商品列表

代码实现

#include<bits/stdc++.h>usingnamespacestd;intm,n;// 预算m和商品数量nstructnode{string s;// 商品名intp;// 价格intv;// 优先级boolf;// 标记是否购买}a[1010];// 商品数组// 比较函数1：用于购买策略排序boolcmp(node a,node b){// 首先按优先级v升序排列（v越小优先级越高）if(a.v!=b.v)returna.v<b.v;else{// v相同时，按价格p升序排列（价格越低越优先）if(a.p!=b.p)returna.p<b.p;// v和p都相同时，按商品名字典序升序排列elsereturna.s<b.s;}}// 比较函数2：用于输出时按商品名字典序排序boolcmp2(node a,node b){returna.s<b.s;}intmain(){// 输入预算和商品数量cin>>m>>n;// 输入商品信息并初始化购买标记for(inti=1;i<=n;i++){cin>>a[i].s>>a[i].p>>a[i].v;a[i].f=false;// 初始化为未购买}// 步骤1：按购买策略排序（优先级->价格->商品名）sort(a+1,a+n+1,cmp);// 步骤2：按照排序顺序尝试购买商品for(inti=1;i<=n;i++){if(m>=a[i].p){// 如果预算足够购买当前商品a[i].f=true;// 标记为已购买m-=a[i].p;// 扣除相应预算}}// 步骤3：为输出做准备，按商品名字典序重新排序sort(a+1,a+n+1,cmp2);// 步骤4：输出所有购买的商品名for(inti=1;i<=n;i++){if(a[i].f){cout<<a[i].s<<endl;}}return0;}

功能分析

1. 数据结构设计

• 使用结构体node存储每个商品的完整信息
• 包含商品名s、价格p、优先级v和购买标记f
• 数组a[1010]存储所有商品，满足N≤1000的数据范围

2. 核心算法流程

• 第一次排序：按照题目要求的购买优先级排序
  • 第一关键字：优先级v（升序，v越小越优先）
  • 第二关键字：价格p（升序，价格越低越优先）
  • 第三关键字：商品名s（字典序升序）
• 购买决策：贪心算法
  • 按排序后的顺序依次考虑每个商品
  • 只要当前预算足够，就购买该商品并更新预算
• 第二次排序：为满足输出要求
  • 按商品名字典序重新排序所有商品
  • 便于按字典序输出购买的商品

3. 时间复杂度分析

• 两次排序：O(N log N)，N≤1000，完全可行
• 一次遍历购买：O(N)
• 总体复杂度：O(N log N)，效率较高

4. 示例验证

输入： 20 4 apple 6 8 bus 15 1 cab 1 10 water 4 8 排序后购买顺序： 1. bus (v=1, p=15) -> 购买，预算剩余5 2. apple (v=8, p=6) -> 预算不足，跳过 3. water (v=8, p=4) -> 购买，预算剩余1 4. cab (v=10, p=1) -> 购买，预算剩余0 按字典序输出： bus cab water

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

#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;}