Approach
Sorting and greedy selection
For ABC246 C — Coupon, the implementation first exposes a useful order, then scans that order while making locally justified choices.
- Choose the key that reveals the greedy or grouping structure.
- Sort the relevant records by that key.
- Scan in order, maintaining the invariant that makes each local choice safe.
Code notes
- 50 lines of C++ from the credited upstream file abc246_c.cpp.
- The implementation visibly relies on sequence storage.
- 3 loop blocks detected.
Complexity
Sorting is typically the dominant term unless the subsequent scan uses a more expensive nested operation.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
1#include <algorithm>2#include <iostream>3#include <vector>4 5using namespace std;6 7int main() {8 unsigned int n;9 int k, x;10 cin >> n >> k >> x;11 12 vector<int> a(n, 0);13 unsigned long ans = 0;14 for (auto& aa : a) {15 cin >> aa;16 ans += aa;17 }18 19 sort(a.rbegin(), a.rend());20 21 unsigned int i = 0;22 while (k > 0 && i < n) {23 if (a[i] - x < 0) {24 i++;25 continue;26 }27 28 ans -= x;29 a[i] = a[i] - x;30 k--;31 }32 33 if (k == 0) {34 cout << ans << endl;35 return 0;36 }37 38 sort(a.rbegin(), a.rend());39 i = 0;40 while (k > 0 && i < n) {41 if (a[i] <= 0) {42 i++;43 }44 ans -= a[i];45 k--;46 a[i] = max(a[i] - x, 0);47 }48 49 cout << ans << endl;50}