天使とふすま [技術室奥プログラミングコンテスト #3 F]

https://beta.atcoder.jp/contests/tkppc3/tasks/tkppc3_f

前提知識

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

考察過程

1. とりあえずDPを考えてみるが難しそう
2. 特殊なソートをする典型適用するやつか？と予想を立てる
3. 実装すると通る

解説

https://beta.atcoder.jp/contests/tkppc3/submissions/2850392

ふすまの順番を貪欲に決めよう。
貪欲といっても一定のルールに基づいてソートを行うことで最適なふすまの順番を特定しよう。
この方針は典型ではあるが、知っていないとこの解法にたどり着くのは難しいかもしれない。
　
ふすまiとふすまjの2つを考えてみる。
ijの順でふすまを配置したい場合はふすまjをA[i]分動かす必要がある。
つまり、A[i]*B[j]だけコストがかかる。
もし、jiの順でふすまを配置した場合のコストA[j]*B[i]の方がコストが小さいなら、その順番となっている方がいい。
つまり、全ての要素についてi＜jならばA[i]*B[j]≦A[j]*B[i]が満たされている必要がある。
このルールを評価関数にして、ソートしよう。
すると、最適なふすまの順番が得られるので、後はその順番を実現するのにかかるコストを計算すると答え。

int N; ll A[201010], B[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i] >> B[i];

    vector<int> ord;
    rep(i, 0, N) ord.push_back(i);
    sort(all(ord), [&](int a, int b) {
        ll x = A[a] * B[b];
        ll y = A[b] * B[a];
        return x < y;
    });

    ll ans = 0;
    ll sm = 0;
    rep(_, 0, N) {
        int i = ord[_];
        ans += sm * B[i];
        sm += A[i];
    }
    cout << ans << endl;
}