Blog·Tanky WooABOUTRSS

HDOJ 1203 I NEED A OFFER!

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

HDOJ 1009FatMouse's Trade 基本上一摸一样吧。。。

题目地址: http://acm.hdu.edu.cn/showproblem.php?pid=1203 所以这题就不写思路了,可以参考HDOJ 1009。

 // Author: Tanky Woo
// HDOJ 1203
// Accepted 1203 0MS 228K 854B C++ Tanky Woo 
#include 
#include 
using namespace std;
// www.wutianqi.com
double result;
int n, m;
typedef struct Offer
{
    int ai;   // 需要费用
    double bi;  // 拿到offer概率
    double ci;   //概率除以费用的比例
}Offer;

Offer offer[1001];

int cmp(Offer a, Offer b)
{
    return a.ci>b.ci;
}

int main()
{
    //freopen("input.txt", "r", stdin);
    while(scanf("%d %d", &n;, &m;) && (m || n))
    {
        //memset(offer, 0, sizeof(offer));
        for(int i = 0; i < m; ++i)
        {
            scanf("%d %lf", &offer;[i].ai, &offer;[i].bi);
            offer[i].ci = offer[i].bi/offer[i].ai;
        }
        sort(offer, offer+m, cmp);
        int cnt = 0;
        result = 1.0;
        while(n >= offer[cnt].ai && cnt <= m-1)   //汗,一个'='号害我找了10几分钟,差点没心情去踢球了
        {
            n -= offer[cnt].ai;
            result *= (1.0 - offer[cnt].bi);
            cnt++;
        }
        printf("%.1lf%%\n", (1.0-result)*100);
    }
    return 0;
}