题意很简单。
有n个牛在FJ的花园乱吃。
所以FJ要赶他们回牛棚。
每个牛在被赶走之前每秒吃Di个花朵。赶它回去FJ要花的时间是Ti。在被赶走的过程中牛就不能乱吃了
那么其实我第一感觉就是跟比率有关。
然后简略的证了一下。
假设序列都由二元组组成，二元组是由D和T组成，那么对一个序列有相邻的两头牛是这样的
..........(a, b) ,(c, d)....................
如果(a,b)和(c,d)交换位置了
变成新序列
..........(c,d),(a,b).....................
假设在这之前FJ已经花了x时间了。
那么赶完这两头牛的损失的量就分别为
x*b + (x + a ) * d
x*d +(x + c) * b
二者做差
得到ad - bc
若ad < bc 则有第一个序列优于第二个
那么这不就是比率么
那么对于任意的序列，我们都可以通过若干次这种相邻的交换使得序列变成最优的。
所以证明完毕。
12年金华赛区的某道签到题就是这个吧。当时直接猜的结论，也没有证明，实际上也证明也很简单吧。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
#include <queue>
#include <algorithm>
#define MAXN 111111
#define MAXM 222222
#define INF 1000000000
using namespace std;
struct node
{int x, y;
}a[MAXN];
int n;
bool cmp(node x, node y)
{return x.x * y.y < x.y * y.x;
}
int main()
{scanf("%d", &n);for(int i = 0; i < n; i++){scanf("%d%d", &a[i].x, &a[i].y);a[i].x *= 2;}sort(a, a + n, cmp);long long ans = 0;long long sum = 0;for(int i = 0; i < n; i++){ans += sum * (long long)a[i].y;sum += a[i].x;}printf("%I64d\n", ans);return 0;
}