题解：B4104 [CSP-X2024 山东] 购物

· · 题解

B4104 [CSP-X2024 山东] 购物 题解

题意

题意很明确，就不过多赘述了。

Solution

首先需要发现优惠券可转化为 m 件物品打包成了一个价格为 w 的物品，因此只要把它和先前 m 件物品的总和比较，贪心的取最小即可。

实现就是先降序排列（大的尽量多用优惠劵），然后遍历序列，m 个数分一组统计总和与 w 比较，选更小的就行。

记得开 long long。

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,w,cnt,ans;
int a[200010];
signed main(){
    cin>>n>>m>>w;
    for(int i=1;i<=n;++i)
        cin>>a[i];
    sort(a+1,a+1+n,greater<int>());//从大到小排序
    for(int i=1;i<=n;++i){
        cnt+=a[i];
        if(i%m==0){
            if(cnt>w) ans+=w;
            else ans+=cnt;
            cnt=0;
        }
    }
    if(cnt>w) ans+=w;
    else ans+=cnt;
    cout<<ans;
    return 0;
}