AtCoder Regular Contest 094: E - Tozan and Gezan
solution
$A_i \lt B_i$なら$(A_i, B_i) \gets (0, B_i - A_i)$にしてよくて、差分の$B_i - A_i$を使って他の$A_j \ge B_j$な$A_j$を減らして$A_j \lt B_j$を作れる。減らす$A_j$の選択は雰囲気でいい感じにやる。$O(n \log n)$。
note
- 雰囲気で通した 3
- 想定解「$A_i \gt B_i$な$i$があるならとざん君は$A_i$を最後まで減らさないことでそれ以外をすべて$0$にできる」 それはそう どうして気付かなかったのか
implementation
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < int(n); ++ (i))
#define ALL(x) begin(x), end(x)
using ll = long long;
using namespace std;
ll solve(int n, vector<int> a, vector<int> b) {
if (a == b) return 0;
ll answer = 0;
ll acc = 0;
vector<int> ge;
REP (i, n) {
if (a[i] < b[i]) {
answer += b[i];
acc += b[i] - a[i];
a[i] = 0;
b[i] = 0;
} else {
if (b[i] != 0) {
ge.push_back(i);
}
}
}
sort(ALL(ge), [&](int i, int j) { return b[i] > b[j]; });
for (int i : ge) {
if (acc < a[i] - b[i] + 1) continue;
ll delta = min<ll>(acc, a[i] - b[i] + 1);
a[i] -= delta;
acc -= delta - 1;
answer += b[i];
}
return answer;
}
int main() {
int n; scanf("%d", &n);
vector<int> a(n), b(n);
REP (i, n) {
scanf("%d%d", &a[i], &b[i]);
}
ll answer = solve(n, a, b);
printf("%lld\n", answer);
return 0;
}