solution

貪欲。$O(n \log n)$。

適当に並べた列を修正することを考えよう。 隣接する$2$要素$(A_i, B_i)$と$(A_j, B_j)$を考えたとき、これら以外の部分に関わらず$A_i B_j \le A_j B_i$なら$i$が$j$の前であるべき。 この比較は$\frac{A_i}{B_i} \le \frac{A_j}{B_j}$と同値であり、また必ずしも隣接している必要はない。 よって$g(i) = \frac{A_i}{B_i}$の順に使用すれば全体としても最適である。

一般に「隣接する$2$要素$x, y$を考えたとき$g(x), g(y)$の順に並ぶように交換すれば目的関数$F$が改善される」を仮定して「$g(x)$の順に整列するのが最適」を言える。 隣接する$2$要素で交換できるものの交換のみで整列(つまりbubble sort)ができるので、任意の列より整列済みの列の方が小さい。

note

$\frac{A_i}{B_i}$の順でソートするやつはさすがに典型だし蟻本にまったく同じのがありそう

implementation

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < int(n); ++ (i))
#define ALL(x) begin(x), end(x)
using ll = long long;
using namespace std;

int main() {
    // input
    int n; cin >> n;
    vector<int> a(n), b(n);
    REP (i, n) {
        cin >> a[i] >> b[i];
    }

    // solve
    vector<int> order(n);
    iota(ALL(order), 0);
    sort(ALL(order), [&](int i, int j) {
        return a[i] * b[j] < a[j] * b[i];
    });
    ll answer = 0;
    ll acc_a = 0;
    for (int i : order) {
        answer += acc_a * b[i];
        acc_a += a[i];
    }

    // answer
    cout << answer << endl;
    return 0;
}