BDISC - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

Sorting

PROBLEM:

A shop sells N items. The i-th costs A_i. You want to buy all of them.
Buying an item reduces the cost of all future items by 1.
Find the minimum cost of buying all N items.

EXPLANATION:

It’s always better to buy cheaper items first, so that more expensive items are discounted as much as possible.
This is because, if cheap items are discounted too much, the discount “loses value”: once the item’s cost reaches 0, further discounts are pointless.

So, the optimal strategy is quite simple: sort the items in ascending order of cost, and buy them in this order.

Let A_1 \leq A_2 \leq \ldots\leq A_N after sorting.
When the i-th item is purchased, it has been discounted once by every item before it: for a total of i-1 times.
So, its current cost is \max(0, A_i - (i - 1)).

Thus, after sorting, the answer is simply

\sum_{i=1}^N \max(0, A_i - (i-1))

TIME COMPLEXITY:

\mathcal{O}(N\log N) per testcase.

CODE:

Editorialist's code (C++) 
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);

    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        vector<int> a(n);
        for (int &x : a) cin >> x;
        sort(begin(a), end(a));
        int ans = 0;
        for (int i = 0; i < n; ++i)
            ans += max(0, a[i] - i);
        cout << ans << '\n';
    }
}
1 Like