AtCoder Regular Contest 053 C - 魔法使い高橋君

問題

arc053.contest.atcoder.jp

解法

まず, (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;
}