Protecting the Flowers

Protecting the Flowers

简单贪心。
关键在于怎么最优，单纯的以时间或者食量排序是不行的，应该综合两者来考虑：
假设有牛a和牛b：
①如果先运输牛a再运输牛b：则破坏的花的数量为：2 * Ta * Db
②如果先运输牛b再运输牛a：则破坏的花的数量为：2 * Tb * Da
如果①<②：
则 Ta * Db < Tb * Da

#include<bits/stdc++.h>
using namespace std;
int n;
struct node{
    long long t,d;
}p[2000050];
bool cmp(node a,node b)
{
    return (a.d*1.0/a.t)>(b.d*1.0/b.t);
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)cin>>p[i].t>>p[i].d;
    sort(p,p+n,cmp);
    long long time=0,ans=0;
    for(int i=0;i<n;i++)
    {
        ans+=time*p[i].d;
        time+=2*p[i].t;
    }
    cout<<ans<<endl;


    return 0;
}

本文地址：https://blog.csdn.net/CesareBorgia/article/details/109646312