Different Strokes [全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019 C]

https://atcoder.jp/contests/nikkei2019-qual/tasks/nikkei2019_qual_c

前提知識

• 特殊なソートで最適解を得るテク

解説

https://atcoder.jp/contests/nikkei2019-qual/submissions/4140532

正直ソートの理由は分からないんやけど、典型があるので紹介しておく。
和でソートとか差でソートとか積でソートとかもっとむずいのとかある。
類題を解いてみよう。
ソートしてDPというのもある。
特に順番が決まらないとDPができない場合はソートしようという気持ちになる。

int N, A[101010], B[101010], C[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i] >> B[i];
    rep(i, 0, N) C[i] = A[i] + B[i];
 
    vector<int> ord;
    rep(i, 0, N) ord.push_back(i);
    sort(all(ord), [&](int a, int b) { return C[a] > C[b]; });
 
    ll ans = 0;
    rep(i, 0, N) {
        if (i % 2 == 0) ans += A[ord[i]];
        else ans -= B[ord[i]];
    }
    cout << ans << endl;
}