HDOJ 1203 I NEED A OFFER!

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
 // Author: Tanky Woo
// HDOJ 1203
// Accepted 1203 0MS 228K 854B C++ Tanky Woo 
#include <iostream>
#include <algorithm>
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;
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

发表评论

电子邮件地址不会被公开。 必填项已用*标注