Protecting the Flowers

题意：有n只奶牛在吃花，为了减少花的损失，将奶牛放回谷仓去，每只奶牛距离各自的谷仓ti分钟时间的距离，并且每只在花园的奶牛每分钟吃di朵花，一次只能放一只奶牛回去，由于回去回来，所以需花费2*ti的时间，求奶牛最少吃多少花？

思路：当AB二只奶牛回去顺序相邻时,我们可以发现AB前面的奶牛和AB后面的奶牛吃的花不变，设AB前面花的时间为T，所以当A一定在B之前时需满足
T * da+(T+ta) * db < T * db+(T+tb) * da
化简为ta * db < tb * da
所以按ta * db < tb * da 排序计算即可。

代码：

#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define inf 1000000007

struct w
{
    int t, d;
}w[100005];

bool cmp(struct w a,struct w b)
{
    return a.t*b.d<b.t*a.d;
}

int main()
{
    int n;
    scanf("%d",&n);
    ll sum=0;
    for(int i=0;i<n;i++)
    {
        scanf("%d%d",&w[i].t,&w[i].d);
        sum=sum+w[i].d;
    }
    sort(w,w+n,cmp);
    ll z=0;
    for(int i=0;i<n;i++)
    {
        sum=sum-w[i].d;
        z=z+sum*2*w[i].t;
    }
    cout << z << endl;
    return 0;
}