poj 3262 牛毁坏花问题贪心算法

题意：有n头牛，每头牛回去都需要一定时间，如果呆在原地就会毁坏花朵。问:怎么安排使得毁坏的花朵最少？

思路：

拉走成本最高的。

什么是成本？毁坏花朵的数量。
例如有两种排序 (这里用(a,b)表示题意，a表示往回走的时间，b表示呆在原处毁坏花朵的数量

(a,b) (c,d) 成本为 x*b+(x+a)*d;

(c,d) (a,b) 成本为 x*d+(x+c)*b;

两种成本显示，如果ad>bc则选择下面那种排序，如果bc>ad则选择上面那种排序，实现的代码

bool cmp(Cow a, Cow b)

{

    return a.d / a.t > b.d / b.t;

}

通过这种成本由高到低的排序，只要遍历，时间*毁坏的花朵累加既可以得到答案

解决问题的代码：

#include <iostream>

#include <algorithm>

#include <cstdio>

using namespace std;

struct Cow

{

    double t, d;

}cow[];

bool cmp(Cow a, Cow b)

{

    return a.d / a.t > b.d / b.t;

}

int main()

{

    int n;

    scanf("%d", &n);

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

        scanf("%lf%lf", &cow[i].t, &cow[i].d);

    sort(cow, cow + n, cmp);

    long long sum = , ans = ;

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

    {

        sum += ans *  * cow[i].d;

        ans += cow[i].t;

    }

    printf("%d\n", sum);

    return ;

}

巴特西

poj 3262 牛毁坏花问题贪心算法

最新文章

热门文章

巴特西

poj 3262 牛毁坏花问题 贪心算法

最新文章

热门文章

poj 3262 牛毁坏花问题贪心算法