AtCoder Regular Contest 053 C - 魔法使い高橋君
解法
まず, (a1, b1) (ただし a1 < b1), (a2, b2) (ただし a2 > b2) という二つの組があった場合, (a1, b1) を先に並べるのが得です。
これは, max(a1, a1-b1+a2), max(a2, a2-b2+a1) を比較すればわかります。(a1 <= a2-b2+a1, a1-b1+a2 <= a2)
ということで, 並べ方としては,
- (a, b) (ただし a < b) を並べていく(前半戦)
- (a, b) (ただし a >= b) を並べていく(後半戦)
という順序になります。後は上記の 2 グループの並べ方を考えれば良いだけです。
まず前半戦ですが, これは a が小さい順に並べるのが得なことは明らかです(上と同じ感じで示せる)。
で, 後半戦ですが, これも本質的には前半戦と同じです。最終的に行き着く先は, sum(a)-sum(b) です。そうすると, さっき a を小さい順に並べるといったのは, 「後ろから見たとき b を小さい順に並べる」すなわち b を大きい順に並べるということと同じです。
以上の貪欲をすると解けます。
const int MAXN = 100100; int n; int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> n; vector<pii> minus, plus; for (int i = 0; i < n; i++) { int a, b; cin >> a >> b; if (a-b < 0) { minus.emplace_back(a, a-b); } else { plus.emplace_back(b, a-b); } } sort(minus.begin(), minus.end()); sort(plus.rbegin(), plus.rend()); ll now = 0, ans = 0; for (auto p : minus) { ans = max(ans, now+p.first); now += p.second; } for (auto p : plus) { ans = max(ans, now+p.first+p.second); now += p.second; } cout << ans << endl; return 0; }