【每日一题】【5月28日】Protecting the Flowers

题意：

有 头奶牛在践踏花田，第 头牛每分钟会毁坏 朵花，把第 头牛关进栅栏里需要 分钟。关进栅栏的过程中，不会毁坏花朵。
同一时间只能处理一头牛，问怎样安排可以使得被毁坏的花朵数目最少。

题解：

贪心。
比较典型的贪心题目。因为同一时间只能处理同一头牛，所以我们只需要确定顺序即可。
确定顺序再结合求最小，就可以想想是不是贪心。

对于这类题：可以通过比较第 个和第 个，或者比较第 头牛或者第 个，怎样的顺序会更优。即确定一个偏序关系。

这里比较一下第 个和第 个的顺序。 和 这两部分的毁坏花朵数数与 和 的顺序无关。
记前 头牛处理完的时间为 。
那么若 排在 前面，这两头牛的毁坏数为 ，
若 排在 前面，毁坏总数为 。
我们要排列后最优，即 排 前面优于 排 后面。
有： ，
化简一下，得到 。
因此按 从小到大排列即可。

Code：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
struct Node {
    int t, d;
    bool operator < (const Node &b) const {
        return t * b.d < b.t * d;
    }
}a[N];
int n;
int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i].t >> a[i].d;
    sort(a + 1, a + n + 1);
    long long ans = 0, tim = 0;
    for(int i = 1; i <= n; i++) {
        ans += tim * a[i].d;
        tim += 2 * a[i].t;
    } 
    cout << ans << endl;
    return 0;
}