这篇博客是从旧博客 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;
}