B4104 [CSP-X2024 Shandong] Shopping - Solution

179 words

1 minute

B4104 [CSP-X2024 Shandong] Shopping - Solution

2024-12-28

Algorithm

Solution

/

C++

/

普及− (Common)

/

CSP-X Elementary Group

Problem Description#

Original Problem has already stated the problem clearly, so no further explanation is needed here.

Approach#

First, sort all products in descending order by price. Then, group them into sets of $m$ items. For each group, add to the answer the minimum value between the original total price of the $m$ products and the discounted price $w$ .

Note! The last group might be incomplete, so special handling is required.

Code#

1
#include <iostream>
2
#include <algorithm>
3
#define ll long long
4
using namespace std;
5
ll a[200005];
6
bool cmp(ll x, ll y)
7
{
8
    return x > y;
9
}
10
int main()
11
{
12
    ll n, m, w, ans = 0, cnt = 0;
13
    cin >> n >> m >> w;
14
    for(int i = 1; i <= n; i++)
15
    {
16
        cin >> a[i];
17
    }
18
    sort(a + 1, a + n + 1, cmp);
19
    for(int i = 1; i <= n; i++)
20
    {
21
        cnt += a[i];
22
        if(i % m == 0)
23
        {
24
            ans += min(cnt, w);
25
            cnt = 0;
26
        }
27
    }
28
    if(cnt >= w)
29
    {
30
        ans += w;
31
    }
32
    else
33
    {
34
        ans += cnt;
35
    }
36
    cout << ans;
37
    return 0;
38
}