Approach
Sorting and greedy selection
For ABC364 C — Minimum Glutton, 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
- 66 lines of C++ from the credited upstream file abc364_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;6using ui = unsigned int;7 8bool comp(pair<ui, long>& l, pair<ui, long>& r) {9 if (l.second != r.second) return l.second > r.second;10 11 return l.first < r.first;12}13 14int main() {15 ui n;16 long x, y;17 cin >> n >> x >> y;18 19 vector<pair<ui, long>> a(n), b(n);20 for (ui i = 0; i < n; i++) {21 cin >> a[i].second;22 a[i].first = i;23 }24 for (ui i = 0; i < n; i++) {25 cin >> b[i].second;26 b[i].first = i;27 }28 29 vector<pair<ui, long>> sa = a;30 vector<pair<ui, long>> sb = b;31 32 long ax = x, ay = y;33 long bx = x, by = y;34 35 sort(sa.begin(), sa.end(), comp);36 sort(sb.begin(), sb.end(), comp);37 38 ui ans = n;39 for (ui i = 0; i < n; i++) {40 41 if (ax >= 0 && ay >= 0) {42 ax -= sa[i].second;43 ay -= b[sa[i].first].second;44 45 if (ax < 0 || ay < 0) {46 ans = i + 1;47 break;48 }49 }50 51 52 if (bx >= 0 && by >= 0) {53 bx -= a[sb[i].first].second;54 by -= sb[i].second;55 56 if (bx < 0 || by < 0) {57 ans = i + 1;58 break;59 }60 }61 }62 63 cout << ans << endl;64 65 return 0;66}