HDOJ 1009 FatMouse’ Trade

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)

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

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
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <algorithm>
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", &trade[i].ji, &trade[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;
}

发布者

Tanky Woo

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

《HDOJ 1009 FatMouse’ Trade》有449个想法

发表评论

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