历年CSP-X复赛真题解析 | B4104 [CSP-X 2024 山东] 购物

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

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

适合人群：

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

附上汇总帖：历年CSP-X复赛真题解析 | 汇总

【题目来源】

洛谷：[B4104 CSP-X2024 山东] 购物 - 洛谷

【题目描述】

双十一，很多人在疯狂地购物。

商家推出了各种各样的优惠活动，吸引顾客购买更多的商品。

某商家推出如下的优惠活动：

该商家共有n nn件商品，单独购买第i ii件商品的费用为a i a_iai​。顾客也可以花费w ww购买 一张优惠券，一张优惠券最多可兑换m mm件商品（无需额外付费）。顾客可以购买任意张优惠券；

如果最后商品不足m mm件，优惠券也可以使用。

求顾客购买完所有n nn件商品的最小费用。

【输入】

第一行有3 33个整数n , m , w n,m,wn,m,w。

第二行有n nn个整数，第i ii个为a i a_iai​，表示第i ii件商品的费用。

【输出】

购买所有商品的最小费用。

【输入样例】

5 2 8 2 7 1 8 4

【输出样例】

15

【算法标签】

《洛谷 B4104 购物》 #山东# #CSP-X小学组# #2024#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong// 使用长整型constintN=200005;// 定义最大数组长度intn,m,w,ans;// n:物品数量，m:分组大小，w:每组最大价值，ans:总价值inta[N];// 存储物品价值signedmain(){cin>>n>>m>>w;// 输入物品数、分组大小和每组价值上限// 读取物品价值并降序排序for(inti=1;i<=n;i++)cin>>a[i];sort(a+1,a+1+n,greater<int>());intres=0;// 当前组累计价值for(inti=1;i<=n;i++){res+=a[i];// 将当前物品加入当前组// 每当凑满m个物品或处理完所有物品时if(i%m==0||i==n){ans+=min(res,w);// 累加当前组价值（不超过w）res=0;// 重置当前组累计价值}}cout<<ans<<endl;// 输出总价值return0;}

【运行结果】

5 2 8 2 7 1 8 4 15