[ACM]hdoj 1009 FatMouse’ Trade

[

Problem Description:
FatMouse prepared M pounds of cat food, ready to trade with thecats guarding the warehouse containing his favorite food,JavaBean.
The warehouse has N rooms. The i-th room contains J[i] pounds ofJavaBeans and requires F[i] pounds of cat food. FatMouse does nothave to trade for all the JavaBeans in the room, instead, he mayget J[i]* a% pounds of JavaBeans if he pays F[i]* a% pounds of catfood. Here a is a real number. Now he is assigning this homework toyou: tell him the maximum amount of JavaBeans he can obtain.
Input:
The input consists of multiple test cases. Each test case beginswith a line containing two non-negative integers M and N. Then Nlines follow, each contains two non-negative integers J[i] and F[i]respectively. The last test case is followed by two -1’s. Allintegers are not greater than 1000.
Output:
For each test case, print in a single line a real number accurateup to 3 decimal places, which is the maximum amount of JavaBeansthat FatMouse can obtain.

题目大概翻译:
肥老鼠有M磅猫粮,想要和看守仓库的猫交换他最喜欢的JavaBean。仓库一共有N间,第i间仓库里包含J[i]磅的JavaBeans,想要得到这些JavaBeans需要付出F[i]磅猫粮作为代价。肥老鼠不必得到房间里所有的JavaBeans。他可以用这个房间需要的猫粮数F[i]的a%,来交换这个房间拥有的JavaBeans数J[i]的a%。需要你计算出肥老鼠最多能够得到多少JavaBeans。
输入大概翻译:
输入将包含多组数据,每一组数据将以两个非负整数M
N开始,然后有N行数据,包含两个非负整数J[i]和F[i]。出现两个-1表示测试数据结束。所有的整数都不超过1000
输出大概翻译:
对于每一个测试数据的情况,输出单独的一行(精确到小数点后三位数)来表示这个肥老鼠可以得到的JavaBeans的最大值。

Sample Input:
5 3
7 2
4 3
5 2
20 3
25 18
24 15
15 10
-1 -1
Sample Output:
13.333
31.500

因为本题想要求解的是肥老鼠最后能的得到的最多的JavaBeans的值。所以我们就要尽量可能的在每个房间拿到多的而且便宜的JavaBeans。因此选择贪心算法。

如何界定便宜,不妨换一个想法,也就是性价比,单位重量的猫粮换到的JavaBeans越多就说明越实惠。
基于这个想法,我就想设定一个变量来保存每个房间的实惠情况。同时为了方便对变量进行有效的管理,在这里我选择将一个房间内的需要的猫粮数、拥有的JavaBeans数、以及实惠情况同意储存在一个struct中。

p表示实惠程度,我选择了用结构数组来表示这个大仓库,每一间小房间就是一个结构体,因为题目中要求每个整数的值都不超过1000因此将整个仓库的大小设置为1000(这样做是使用了food_N[0],如果不想使用food_N[0]数组则需要声明为1001),实惠程度的具体计算方法:

在计算出实惠程度之后,因为肥老鼠的目的是得到最多的JavaBeans因此我们需要找出最实惠的房间多换取一点JavaBeans。所以下一步我们需要将实惠程度进行由大到小的排序。首先选择了比较笨拙的冒泡排序法,发现效率一般般的冒泡排序法竟然没有超时,这个让我很惊讶

接下来是基于C++的sort排序

明显代码简洁了很多。
现在实惠程度的排序也已经完成了,可以让肥老鼠去换了,按照实惠程度从最实惠的一个房间开始换走最实惠房间内的所有JavaBeans,依次向下进行,直到自己的猫粮用完。如果出现猫粮不足以完全换走JavaBeans的情况时,本着有多少换多少的原则进行即可。

一旦肥老鼠的猫粮用完了立刻用break来跳出循环。
本题目的完整代码(冒泡版):

本题完整代码(sort版):

 

About the author

NOBUG.IN

Add comment

By NOBUG.IN

Your sidebar area is currently empty. Hurry up and add some widgets.