Tanky WooRSS

HDOJ 1009 FatMouse' Trade

21 Jul 2010
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

AC了题目的心情总是格外的好。呵呵。

这个类型的贪心题算是经典的经典的。 题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1009

题意是用猫粮换javabean。可以按比例兑换(还有其他类型题目不能按比例换的,注意了)

思路:先j[i]/f[i]的比例进行由大到小的排序。然后依次减去f[i],获得值加上j[i]。这里要考虑几种情况。

1.M值减到一定程度后,不够换一个房间的的javabean,这里就只能把剩下的M按比例换了。

2.全部换完M还有多余的。剩余的就不管。(这里先没注意,只判断M是否小于0,结果 Output Limit Exceeded)

好了,剩下的就是贴代码了:

#include 
#include 
using namespace std;
// Author: Tanky Woo
// 31MS 212K 1174B 
typedef struct TRADE{
    int ji;   // javabean
    int fi;   // cat food
    double scale;  // 比例
}TRADE;

TRADE trade[1000];
int M, N;

int cmp(TRADE a, TRADE b)
{
    return (a.scale > b.scale);   //从大到小
}

int main()
{
    //freopen("input.txt", "r", stdin);
    while(scanf("%d %d", &M;, &N;) && !(M == -1 && N == -1))
    {
        //printf("1\n");
        memset(trade, 0, sizeof(trade));
        for(int i = 0; i < N; ++i)
        {
            scanf("%d %d", [i].ji, [i].fi);
            trade[i].scale = double(trade[i].ji)/trade[i].fi;

        }
        sort(trade, trade+N, cmp);
        /*
        for(int i = 0; i < N; ++i)
            printf("%d %d %lf\n",trade[i].ji, trade[i].fi, trade[i].scale);
            */
        int cnt = 0;
        double sum = 0.0;

        while(M > 0 && cnt < N)
        {
            if(M >= trade[cnt].fi)
            {
                sum += trade[cnt].ji;
                M -= trade[cnt].fi;
            }
            else
            {
                sum += double(M)/trade[cnt].fi*trade[cnt].ji;
                M = 0;
            }
            cnt++;
        }
        printf("%.3lf\n", sum);     
    }
    return 0;
}