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

这道题算是我的贪心入门了，题意大概就是n头牛，农夫要送他们回牛舍，送一只牛回去要ti时间（注意这里是单程的，回来也要Ti），送牛的时候其他牛会在原地吃花，每头牛每单位吃Di朵花，问怎样送牛花被吃得最少。（注意每头牛的Ti，Di都不相同）（如果这个题解对你有用请点点赞鼓励鼓励我哈，谢谢）

思路：

1、其实这题影响的因素就两个，Ti和Di，我们设想两头牛AB,是先送A再送B好还是先送B再送A好，无论先送谁，其实都不影响前面跟后面的牛吃的花数，只会影响AB吃的花数。我们设想：AB优于BA（谁优都可以）

2、设前面的牛被送的时间为X，来回就为2X。

对AB而言： 牛A:吃的花为2X*DA -------- 牛B:吃的花为(2X+Ta)*Db（因为B前面多了个A）

对BA而言： 牛B:吃的花为2X*DB -------- 牛A:吃的花为(2X+Tb)*DA 得出如此式子

3、得出式子后因为要让花吃的尽可能少所以我们不是单笔一只牛，而是两只牛加起来一起比，因为设想的是AB优于BA所以2X*DA+(2X+Ta)Db < 2XDB+(2X+Tb)*DA,化解得出应该为 Ta/Da < Tb/Db;得出这个公式就已经解出最核心的问题了，就是我们应该排序，把牛牛按照Ti/Di结果小的排前面的规则进行排序

4、按照排序后把每只猪要等待的时间算出来，再算出他吃的花的数量进行累加，最后的出答案，下面是完整代码

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
struct cow{
    int ti;
    int di;
}a[100005];
int cmp(cow x,cow y){
    return (float)x.ti/x.di < (float)y.ti/y.di; //这里要转为浮点型，不然排序排不准噢
}
int main(){
    IOS;
    int n;cin>>n;
    b[0]=0;
    for(int i=1;i<=n;i++){
        cin>>a[i].ti;
        cin>>a[i].di;
    }
    sort(a+1,a+n+1,cmp);
//     for(int i=1;i<=n;i++){
//         cout<<a[i].ti<<" "<<a[i].di<<endl;
//     }
    long long num=0,sum=0;
    for(int i=2;i<=n;i++){
        num+=(a[i-1].ti);   //num是计算农夫走路的时间（x2就是下一只猪吃花的时间）
        sum+=2*num*a[i].di;  //算出每一只猪吃的时间并且累加，得到最终结果
//         cout<<num<<" "<<sum<<endl;
    }
    cout<<sum;
    return 0;
}