题解 | 护花使者 [贪心 交换论证（Exchange Argument）]

贪心中很重要且典型的一种策略：交换论证。

结论：

存在最优策略序列，使得毁坏花朵总数最少，当且仅当：考虑这个序列中的任意一对相邻点 a，b，若 a 在 b 之前送走，均有 a.time*b.harm<=b.time*a.harm.

证明：

假设存在一种策略序列，存在相邻点 a b 使得 a.time*b.harm>b.time*a.harm，且毁坏花朵总数比上述策略更少。由于 a b 相邻，交换 a b 顺序不会影响其余任何点对结果的贡献。而又由于 a.time*b.harm 大于 b.time*a.harm，交换 a b 后必然使得毁坏花朵总数减少，与假设矛盾，证毕。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, f, ans;
vector<pair<int, int>> a;
bool cmp(pair<int, int>& x, pair<int, int>& y) {
    return x.first*y.second<y.first*x.second;
}
signed main() {
    cin>>n;
    for(int i=1; i<=n; i++) {
        int x, y; cin>>x>>y;
        f+=y;
        a.push_back({x, y});
    }
    sort(a.begin(), a.end(), cmp);
    for(auto &[x, y]: a) {
        f-=y;
        ans+=2*x*f;
    }
    cout<<ans;
}