POJ Protecting the Flowers

题目大意

奶牛要吃花，FJ来赶牛，将第i头牛赶走要2*ti分钟，奶牛每分钟吃di个单位花，求花的最小损失

先赶吃花多的，Wrong Answer QAQ

我们可以算一算损失

设sum=d1+d2+d3+…+dn

那损失为：

cost1=sum⋅2∑ni=1ti−(sum−d1)⋅2∑ni=2ti−(sum−d1−d2)⋅2∑ni=3ti...

如果将1号牛与2号牛交换

那损失为：

cost2=sum⋅2∑ni=1ti−(sum−d2)⋅2(t1+∑ni=3ti)−(sum−d1−d2)⋅2(∑ni=3ti)...

有变化的量为：t1·d2 –> t2·d1

假设cost1 > cost2

即 t1·d2 > t2·d1

所以t1d1>t2d2

所以在排序时，t1d1小的优先赶走

代码如下：

#include<cstdio>

#include<cmath>

#include<cstring>

#include<queue>

#include<algorithm>

using namespace std;

struct node{

    int t,d;

}a[100001];

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

int getint()

{

    int num=0,flag=1;char c;

    while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;

    while(c>='0'&&c<='9')num=num*10+c-48,c=getchar();

    return num*flag;

}

int n;

long long ans,t;

int main()

{

    int i;n=getint();

    for(i=1;i<=n;i++)a[i].t=getint(),a[i].d=getint();

    sort(a+1,a+n+1,cmp);

    for(i=1;i<=n;i++)

    {

        ans+=a[i].d*t;

        t+=2*a[i].t;

    }

    printf("%lld",ans);

}

巴特西

POJ Protecting the Flowers

最新文章

热门文章