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

题意

题目中已经表达的很明白了，在此就不在赘述了。

思路

先将所有商品按照价格降序排序，之后每 $m$ 个一组，答案加上这 $m$ 个商品的原价与优惠价格 $w$ 取最小值。

注意！最后一组有可能没算完，所以需要特判一下。

Code

#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
ll a[200005];
bool cmp(ll x, ll y)
{
    return x > y;
}
int main()
{
    ll n, m, w, ans = 0, cnt = 0;
    cin >> n >> m >> w;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    sort(a + 1, a + n + 1, cmp);//从大到小排序。
    for(int i = 1; i <= n; i++)
    {
        cnt += a[i];
        if(i % m == 0)//每m个一组
        {
            ans += min(cnt, w);
            cnt = 0;
        }
    }
    if(cnt >= w)//如果最后一组没算完
    {
        ans += w;
    }
    else
    {
        ans += cnt;
    }
    cout << ans;
    return 0;//return 0好习惯
}