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; }