HDU 1009 FatMouse' Trade题解

5 3
7 2
4 3
5 2
20 3
25 18
24 15
15 10
-1 -1

13.333
31.500

贪心法水题，

个人觉得这句话难理解：he may get J[i]* a% pounds of JavaBeans if he pays F[i]* a% pounds of cat food

这样表达可以购买几分之几的。

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
struct twoInts
{
	int j, f;
	bool operator<(const twoInts two) const
	{
		double a = (double)j / (double)f;
		double b = (double)two.j / (double)two.f;
		return a > b;
	}
};

int main()
{
	int M, N;
	while (scanf("%d %d", &M, &N) && -1 != M)
	{
		vector<twoInts> vt(N);
		for (int i = 0; i < N; i++)
		{
			scanf("%d", &vt[i].j);
			scanf("%d", &vt[i].f);
		}
		sort(vt.begin(), vt.end());
		double maxBean = 0.0;
		for (int i = 0; i < N; i++)
		{
			if (M >= vt[i].f)
			{
				maxBean += vt[i].j;
				M -= vt[i].f;
			}
			else
			{
				maxBean += (double)vt[i].j * M / (double)vt[i].f;
				break;
			}
		}
		printf("%.3lf\n", maxBean);
	}
	return 0;
}

HDU 1009 FatMouse' Trade题解,布布扣,bubuko.com

HDU 1009 FatMouse' Trade题解

原文：http://blog.csdn.net/kenden23/article/details/31418535