牛客—— Protecting the Flowers （贪心）

牛客—— Protecting the Flowers （贪心）

题意：

农夫有n头牛在破坏花朵，每头牛每分钟破坏d[i]朵花，农夫把这头牛运回牛棚的时间为t[i]（单程）,问如何运才能使得被破坏的花最少。

思路：

考虑贪心。

其实贪心无非几种排序关键字，某单个数值，某些数值之加减乘除。

对于本题，我们选择完两个牛，无论怎么排序，时间都是(t[1]+t[2])*2,，对后续的时间没有影响，所以我们只需要考虑如何安排这两头牛的顺序使得花被破坏的最少。

在两头牛中考虑的话，假设这两头牛为牛1和牛2，不难想到可以根据单位时间破坏花的数量来进行从大到小的排序，首先送走的是单位时间破坏花的数量最多的牛才能使得花受的破坏尽可能的少。

证明的话，看网上有这种思路：(一般贪心都会AC)

如果先送1再送2的话，损失的花的数量就是2 * t[1] * d[2];

如果先送2再送1的话，损失的花的数量就是2 * t[2] * d[1];

所以如果想要先送1再送2，就必须满足2 * t[1] * d[2] < 2 * t[2] * d[1];

即t[1] * d[2] < t[2] * d[1] (好像根据这个更简单)

移项后可得 d[1] / t[1] > d[2] / t[2] （这个的实际意义好理解）

但是要注意比较的时候化为double类型

代码:

#pragma GCC optimize(2)
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
typedef pair<int,int>PII;

inline ll read(){
    ll x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = (x<<1) + (x<<3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

const int maxn=1e6+100;

struct node{
    int t,d;
    bool operator < (const node &a)const{
        return d*1.0/t>a.d*1.0/a.t;
    }
}a[maxn];

int main(){
    int n;
    n=read();
    for(int i=0;i<n;i++) a[i].t=read(),a[i].d=read();
    sort(a,a+n);
    ll resd=0,rest=0;
    for(int i=0;i<n;i++){
        resd+=a[i].d*rest;
        rest+=a[i].t*2;
    }
    printf("%lld\n",resd);
    return 0;
}