problem

有n头牛在吃花，第i头牛每分钟吃的花，John每次可以运走一头牛，运走第i头牛需要的时间是。设计一种运牛的顺序，使得被吃掉的花最少。

solution

非常经典贪心题。

先考虑只有两头牛的情况。如果先运走，那么被吃掉的花就是，同理如果先运走被吃掉的花就是。所以我们按照排序，然后统计答案就行了。

code

/*
* @Author: wxyww
* @Date:   2020-05-27 22:08:27
* @Last Modified time: 2020-05-27 22:09:59
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
#include<cmath>
using namespace std;
typedef long long ll;
const int N = 100010;
ll read() {
    ll x = 0,f = 1;char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1; c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0'; c = getchar();
    }
    return x * f;
}
struct node {
    int t,d;
}a[N];
bool cmp(const node &A,const node &B) {
    return A.t * B.d < B.t * A.d;
}
int main() {
    int n = read();
    for(int i = 1;i <= n;++i) a[i].t = read(),a[i].d = read();

    sort(a + 1,a + n + 1,cmp);


    int now = 0;
    ll ans = 0;
    for(int i = 1;i <= n;++i) {
        ans += now * a[i].d;
        now += a[i].t + a[i].t;
    }
    cout<<ans<<endl;
    return 0;
}