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好习惯
}