【题解】FatMouse‘ Trade

题目链接：FatMouse‘ Trade

写在前面:

很水的水题 ，每次做都会莫名其妙载个跟头，一时半会还看不出来。 看来是有bear来，搞偷袭hhh

题意:

给定n个房间和m个金币，每个房间有J[i]个奶酪，但是要用F[i]个金币购买。问最多可以得到多少奶酪？答案是个实数。

思路:

贪心，根据性价比排序。

ps:

我们在排序时是用实数排序的，后面在计算奶酪的时候很容易用之前算出的单价来乘金币个数，但是这样是不对的，因为用整数得到实数已经有了数据损失，再乘回去数据损失会更大。只有最后金币不够买一整个房间的奶酪时才可以这么做。

AC代码:

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#include<set>
#include<map>

using namespace std;
const int N = 1010,INF=0x3f3f3f3f;
typedef pair<int, int> PII;
typedef long long ll;

int n, m;
pair<double,PII> p[N];
int main()
{
	while (cin >> m >> n && (n !=-1 && m !=-1))
	{
		for (int i = 0; i < n; ++i)
		{
			cin >> p[i].second.first >> p[i].second.second;
			p[i].first = p[i].second.first / (double) p[i].second.second;
		}

		sort(p, p + n);

		double sum = 0;
		for (int i = n-1; i >= 0; --i)
		{
			if (m >= p[i].second.second)
			{
				sum += (double)p[i].second.first;
				m -= p[i].second.second;
			}
			else
			{
				sum += (double) m * p[i].first;
				break;
			}
		}

		printf("%.3lf\n", sum);
	}

	return 0;
}