news 2026/2/27 12:35:34

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

作者头像

张小明

前端开发工程师

1.2k 24
文章封面图
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;}
版权声明: 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：809451989@qq.com进行投诉反馈，一经查实，立即删除！
网站建设 2026/2/25 8:33:34

广汽传祺：lora-scripts生成大湾区文化融合画面

广汽传祺&#xff1a;LoRA-Scripts生成大湾区文化融合画面 在粤港澳大湾区这片科技与人文交汇的热土上&#xff0c;传统骑楼与现代天际线并肩而立&#xff0c;粤剧唱腔与智能语音助手同频共振。作为扎根于此的高端汽车品牌&#xff0c;广汽传祺面临的不仅是产品竞争&#xff0c…

作者头像 李华
网站建设 2026/2/16 2:14:43

告别旧写法！C++26中优先级队列的8种现代C++用法

第一章&#xff1a;C26优先级队列的核心演进与新特性C26 对标准库中的优先级队列&#xff08;std::priority_queue&#xff09;进行了显著增强&#xff0c;引入了更灵活的接口设计和底层容器可定制化机制&#xff0c;提升了性能控制粒度与使用场景适配能力。支持异构比较器的模…

作者头像 李华
网站建设 2026/2/24 17:24:13

为什么顶尖团队都在用C++26做CPU绑定？99%开发者忽略的关键细节

第一章&#xff1a;C26 CPU亲和性绑定的演进与意义随着多核处理器架构的普及&#xff0c;程序对底层硬件资源的控制需求日益增强。C26 标准在并发与系统级编程方面迈出了关键一步&#xff0c;正式引入了标准化的 CPU 亲和性绑定机制&#xff0c;使得开发者能够在语言层面直接控…

作者头像 李华
网站建设 2026/2/24 13:39:11

【限时揭秘】金融级Java系统预测架构：实现99.99%可用性的背后技术

第一章&#xff1a;Java智能运维预测模型概述 在现代企业级应用中&#xff0c;Java 作为核心开发语言广泛应用于后端服务。随着系统复杂度的提升&#xff0c;传统运维方式已难以满足高可用性与故障预警的需求。智能运维&#xff08;AIOps&#xff09;结合机器学习与大数据分析技…

作者头像 李华
网站建设 2026/2/25 12:56:43

蜻蜓FM内容包装升级：lora-scripts辅助视觉识别体系

蜻蜓FM内容包装升级&#xff1a;lora-scripts辅助视觉识别体系 在音频内容平台竞争日益白热化的今天&#xff0c;用户注意力成了最稀缺的资源。蜻蜓FM作为国内头部音频平台&#xff0c;早已意识到一个残酷现实&#xff1a;光有优质的声音内容远远不够——听觉体验必须与视觉表达…

作者头像 李华