hdu 2111 Saving HDU

解题思路：

首先做本题，要清楚题意的要求。

1.读取数据到结构体数组中，然后按其价值降序（价值最大的放在最上面）。

2.比较给定的M (包裹容量），如果大于当前宝物的体积，则计算总价值+= 宝物的总价值（体积*价值），然后将当前总容量=总容量 - 已消耗宝物的体积

3.如果当前剩余容量，不大于宝物体积，则【假设宝贝可以分割，分割后的价值和对应的体积成正比】，总价值+=m*当前宝物的价值。

4. 输出总价值

AC 代码：

#include<stdio.h>

#include<stdlib.h>

typedef struct

{

    int val,v;

} B;

int cmp(const void *a,const void *b)

{

    B *a1=(B *)a;

    B *b1=(B *)b;

    return b1->val - a1->val;

}

int main(void)

{

    int i,m,n,sum;

    B b[110];

    while(scanf("%d",&m)!=EOF,m)

    {

        scanf("%d",&n);

        sum=0;

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

            scanf("%d%d",&b[i].val,&b[i].v);

        qsort(b,n,sizeof(b[0]),cmp);

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

        {

            if(m>b[i].v)

            {

                sum+=b[i].v*b[i].val;

                m-=b[i].v;

            }

            else

            {

                sum+=m*b[i].val;

                break;

            }

        }

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

    }

    return 0;

}

巴特西

hdu 2111 Saving HDU

最新文章

热门文章