20190630A（贪心）

题目描述

约翰留下他的N只奶牛上山采木。他离开的时候，她们像往常一样悠闲地在草场里吃草。
可是，当他回来的时候，他看到了一幕惨剧：牛们正躲在他的花园里，啃食着他心爱的美丽花朵！为了使接下来花朵的损失最小，约翰赶紧采取行动，把牛们送回牛棚。
牛们从1到N(2≤N≤100000)编号．第i只牛所在的位置距离牛棚Ti(1≤Ti≤2000000)分钟的路程，而在约翰开始送她回牛棚之前，她每分钟会啃食Di(1≤Di≤100)朵鲜花。
无论多么努力，约翰一次只能送一只牛回棚。而运送第第i只牛事实上需要2Ti分钟，因为来回都需要时间。
写一个程序来决定约翰运送奶牛的顺序，使最终被吞食的花朵数量最小。

输入

第1行输入N；
之后N行每行输入两个整数Ti和Di。

输出

输出一个整数，表示最小数量的花朵被吞食。

样例输入 Copy

样例输出 Copy

86
强烈要求改变题面意思！奶牛在Fj过去的路程中就被吓傻了！她们不会在这时吃花！
第一反应最优解，先dp吧，但是发现貌似没有这么麻烦。。。样例贪心就可以过。但是我没有看明白题目，于是就乱搞了一通，把样例水过去就不水了，于是0分。
分析：
继续贪心算法。Fj要吃的花的数量最少，进行假设：牛1牛2，她们的d和t分别用dx，tx，dy，ty来表示。
假设先搬牛1比先搬牛2得出的解更优。  
于是：

xd*xt+(xt+yt)*yd<=yd*yt+(yt+xt)*xd;

xd*xt+xt*yd+yt*yd<=yd*yt+yt*xd+xt*xd;

化简得

xt*yd<=yt*xd

（眼花缭乱）
反正就是cmp按照这个东西排序，就能得到最优的顺序
代码：

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

const int maxn=;

int n;//2 100000

struct node

{

    long long int t,d;

}a[maxn];

long long int t;

long long int ans;

bool cmp(node x,node y)

{

    return x.d*y.t>=y.d*x.t;

}

inline long long read()

{

    long long x=,f=;char s=getchar();

    while(s>''||s<''){if(s=='-')f=-;s=getchar();}

    while(s<=''&&s>=''){x=x*+s-'';s=getchar();}

    return x*f;

}

int main()

{

    n=read();//scanf("%d",&n);

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

    {

        a[i].t=read();

        a[i].d=read();//scanf("%d%d",&a[i].t,&a[i].d);

    }

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

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

    {

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

        t+=a[i].t*;

    }

    printf("%lld",ans);

    return ;

}

（完）

巴特西

20190630A（贪心）

题目描述

输入

输出

样例输入 Copy

样例输出 Copy

最新文章

热门文章