题目链接

Protecting the Flowers POJ - 3262

思路

这是一类套路题，相邻两个互换不影响其他的，所以按相邻两个的最优策略排序即可。

时间复杂度

$$ O(Nlog(N)) $$

代码

#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 1e5 + 10;

int a[MAXN], b[MAXN], id[MAXN];

bool cmp(int x, int y) {
    return a[x] * b[y] - a[y] * b[x] < 0;
}

int main() {
    int n;
    scanf("%d", &n);// don't forget &
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &a[i], &b[i]);// don't forget &
        id[i] = i;
    }
    sort(id + 1, id + 1 + n, cmp);
    long long ans = 0;
    long long t = 0;
    for (int i = 1; i <= n; i++) {
        int x = id[i];
        ans += t * b[x];
        t += 2 * a[x];
    }
    printf("%lld", ans);
    return 0;   
}