hdu 1009 FatMouse'Trade （贪心算法）

问题描述：

FatMouse prepared M pounds of cat food, ready to trade with the cats guarding the warehouse containing his favorite food, JavaBean.

The warehouse has N rooms. The i-th room contains J[i] pounds of JavaBeans and requires F[i] pounds of cat food. FatMouse does not have to trade for all the JavaBeans in the room, instead, he may get J[i]* a% pounds of JavaBeans if he pays F[i]* a% pounds of cat food. Here a is a real number. Now he is assigning this homework to you: tell him the maximum amount of JavaBeans he can obtain.

 胖老鼠准备了M磅的猫粮，准备与守卫（包含他最喜欢的食物JavaBean）的仓库的猫交易。仓库有N个房间。第i个房间包含J [i]磅的JavaBeans并且需要F [i]磅的猫粮。胖老鼠不需要与房间里的所有JavaBeans进行交易，而是，如果他支付F [i] *a％磅的猫粮，他可能会得到J[i]* a% 磅的JavaBeans。这是一个实数。现在他正在为你分配这个任务：告诉他，他可以获得的最大JavaBeans数量。

输入：

 The input consists of multiple test cases. Each test case begins with a line containing two non-negative integers M and N. Then N lines follow, each contains two non-negative integers J[i] and F[i] respectively. The last test case is followed by two -1's. All integers are not greater than 1000.

输入包含多个测试用例。每个测试用例以包含两个非负整数M和N的行开始。然后是N行，每行包含两个非负整数J [i]和F [i]。最后一个测试用例后跟两个-1。所有整数不大于1000。 

输出：

For each test case, print in a single line a real number accurate up to 3 decimal places, which is the maximum amount of JavaBeans that FatMouse can obtain.

 对于每个测试用例，在一行中打印一个实数，最多精确到3个小数位，这是FatMouse可以获得的最大JavaBeans数量。

解题思路：

 既然每个房间的JavaBean和所需要的猫粮可能不一致，即JavaBean/猫粮的比例不一致，比例越大，表示可以花费少量的猫粮获取更多的JavaBean。所以我们可以通过将每个房间的 JavaBean/猫粮 按照从大到小的排序，然后根据所拥有的猫粮数量来依次换取JavaBean。如果房间里的JavaBean/猫粮 比例相同，那么我们应该选取相同比例下能获取到的JavaBean更多的房间，如此便能获得最多的JavaBean。

样例输入：

5  3      拥有5磅猫粮 3个房间

7  2     房间1需要2榜猫粮 获取7磅JavaBean   7/2 = 3.5

4  3     房间2需要3榜猫粮 获取4磅JavaBean   4/3 = 1.33...

5  2     房间3需要2榜猫粮 获取5磅JavaBean   5/2 = 2.5

根据比例房间排序应该是132，因此先用2磅猫粮换取房间1的7磅的JavaBean，然后再用2磅的猫粮换取3号房间的5磅JavaBean。最后剩到1磅的猫粮换取2号房间的 1*4/3 = 1.333 的JavaBean。

因此总的输出是 7+5+1.333 = 13.333 

AC 代码如下 运行时间124MS 运行内存 1896K

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
struct Mouse
{
	double j;//JavaBean  
	double f;//猫粮 
	double a;//j/f的比例值 
};
bool Comp(const Mouse &d1, const Mouse &d2)
{
	if (d1.a != d2.a) //比例不同 返回比例大的 
		return d1.a > d2.a;
	else              //比例相同 返回需要猫粮更少的 
		return d1.f < d2.f;
}
int main()
{
	int m, n, i;
	vector<Mouse>v;
	Mouse mouse;
	cout.precision(3);//输出精确到 3 个小数位 
	double sum;//记录总量 
	while (cin >> m >> n)
	{
		if (m == -1 && n == -1)//循环出口 
			break;
		v.clear();
		sum=0.0; 
		for (i = 0; i < n; i++)//依次输入房间参数 
		{
			cin >> mouse.j >> mouse. f;
			mouse.a = mouse.j/ mouse.f; //JabaBean与猫粮比例 
			v.push_back(mouse); 
		}
		sort(v.begin(), v.end(), Comp); //从小到大排序 
		for (i = 0; i < v.size(); i++) //依次查询房间 
		{
			if (m >= v[i].f) //猫粮充足则交换 
			{
				sum = sum + v[i].j;
				m = m - v[i].f;
			}
			else //猫粮不充足，则按照比例交换 
			{
				sum = sum + m*v[i].a;
				break;
			}
		}
		cout << fixed << sum << endl; //注意输出精度精确到3位小数 
	}
	return 0;
}