题解 | #[USACO 2007 Jan S]Protecting the Flowers#

一道简单的套路题，假设有两头牛a，b，这两头牛交换位置不影响前面的情况和后面的情况，因为无论怎么交换，他们的时间消耗总和都是一样的，可以推导出：当满足ta/da<=tb/db时，a牛在前的情况更优，所以按上述推导的公式从小到大排序，n处的结果就是最后答案。看这个题的数据比较大，又需要乘法，所以判断需不需要高精度，判断以后发现sum的最大值只能是10^13次方，long long可以装下。

#include<iostream>
#include<algorithm>
using namespace std;
int n;
const int M = 1e5 + 5;
struct node {
	long long t, d;
	double div;
	bool operator<(const node& p)const {
		return div < p.div;
	}
}a[M];
long long T[M];
long long sum[M];
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i].t >> a[i].d;
		a[i].div = (double)a[i].t / (double)a[i].d;
	}
	sort(a + 1, a + 1 + n);

	for (int i = 1; i <= n; i++) {
		T[i] = T[i - 1] + 2 * a[i].t;	//时间 
	}

	for (int i = 1; i <= n; i++) {
		sum[i] = sum[i - 1] + a[i].d * T[i - 1];
	}
	cout << sum[n] << endl;
	return 0;
}