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

贪心：
假设如果有两头牛，往返的时间分别是$t_{i}t\_i$，每分钟摧毁的花是$d_{i}d\_i$。
那么我们可以得出：
1.先牵第一头牛，消耗的总数为$t_1\ast d_{2}t\_1*d\_2$
2.先牵第二头牛，消耗的总数为$t_2\ast d_{1}t\_2*d\_1$
我们使第一种情况消耗总数最小，可以列出。
我们根据这个条件排序，再从头模拟就可以得出答案。
如果只考虑$dd$，那么我们可以根据上面的假设判断出，这是错误的想法。
如果$t_1=2,t_2=3,d_1=1,d_2=2t\_1=2,t\_2=3,d\_1=1,d\_2=2$，根据正确分析，应该牵第二头牛；如果只分析$dd$，我们应该选择第一头牛。
AC代码

#include <bits/stdc++.h>
using namespace std;
bool cmp(pair<int, int> a, pair<int, int> b)
{
    return a.first * b.second < a.second * b.first;
}
int main(void)
{
    int n;
    cin >> n;
    vector<pair<int, int>> mp(n);
    for (int i = 0; i < n; i++)
        cin >> mp[i].first >> mp[i].second;
    sort(mp.begin(), mp.end(), cmp);
    long long sum = 0, t = 0;
    for (int i = 0; i < n; i++)
    {
        sum += t * mp[i].second;
        t += 2 * mp[i].first;
    }
    cout << sum << endl;
}