题解 P2878 【[USACO07JAN]保护花朵Protecting the Flowers】

Dawn_Sdy · 2019-05-24 20:51:57 · 题解

显然可以看出此题具有很明显的贪心的特征，那么问题就是我们的贪心策略是什么

我们把其中两只奶牛的运输放在一起看，那么对剩下奶牛的影响与这两头奶牛运输的先后顺序无关，所以取决两头奶牛运输顺序的就是这两头奶牛在不同顺序下的损耗。

我们把这两头牛的时间分别设为x1,x2

把他们的每分钟的食草速度设成y1,y2

那么如果先运奶牛1： 造成的损耗是：x.d * y.t

如果先运奶牛2： 造成的损耗是：y.d * x.t

那么我们得到的排序方式的代码段就是：

bool cmp(node x,node y)
{
    return x.d*y.t>y.d*x.t;
}

然后，记录两个数，sum与time，time用来记录从1到i用的总时间，sum统计答案

AC代码如下：

#include<bits/stdc++.h>
using namespace std;
struct node{
    long long t,d;
}a[1000005];
bool cmp(node x,node y)//排序方式 
{
    return x.d*y.t>y.d*x.t;
}
int main(){
    int n;
    cin>>n;
    for (int i=1;i<=n;i++)
        cin>>a[i].t>>a[i].d;
    sort(a+1,a+n+1,cmp);//排序 
    long long time=0,sum=0;//time统计时间，sum统计答案 
    for (int i=1;i<=n;i++)
        {
        sum+=a[i].d*time;//注意，一定要先统计答案，再统计时间！ 
        time+=a[i].t*2;
        }
    cout<<sum; 
    return 0;
}