老鼠与猫的交易

题目描述

有一只老鼠很喜欢奶酪，但是奶酪被分别放在N个房间里，而且这些房间都有一只猫咪看守，现在它准备和猫咪们做个交易。它有M磅的猫食，想用这M磅猫食换取奶酪。在猫咪看守的每一个房间里有奶酪J[i]磅，同时猫咪需要F[i]磅的食物，如果老鼠给猫咪F[i](a)%的猫食，那么它就可以得到J[i](a)%的奶酪。现在已知每只猫咪对猫食的需求量和每个房间的奶酪数，那老鼠怎样才能换得最多的奶酪呢？

输入格式

第一行输入两个正整数M和N（M和N不大于10000），后面跟N行（每个房间的奶酪数和猫食的需求量）。

输出格式

输出老鼠得到的最多的奶酪数，保留三位小数。

样例

样例1输入

5 3
7 2
4 3
5 2

样例1输出

13.333

样例2输入

20 3
25 18
24 15
15 10

样例2输出

31.500

题解

读完题，我们做基本信息处理

const int M = 1e4 + 5;
int m, n;

struct room{
	int cat_food;
	int cheese;
}a[M];

scanf("%d %d", &m, &n);
for(int i = 1; i <= n; i ++) {
	scanf("%d %d", &a[i].cheese, &a[i].cat_food);
}

然后我们大致可以想到这是一道水贪心题，
题中有两个量，奶酪数量和猫粮数量，
作为一个吝啬(咳咳)合格的买家，
我们当然想要花更少的猫粮买到更多的奶酪，
因此，我们以奶酪与猫粮的比值大小为标准，
从大到小排序

bool cmp(room x, room y) {
	return double(x.cheese) / x.cat_food > double(y.cheese) / y.cat_food;
}

sort(a + 1, a + 1 + n, cmp);

最后我们不断叠加买到的奶酪和卖出的猫粮

for(int i = 1; i <= n; i ++) {
		temp += a[i].cat_food;
		tot += a[i].cheese;
}

当然最后也要尽力买到奶酪

if(temp + a[i].cat_food > m) {
	double num = m - temp;
	double pro = num / a[i].cat_food;
	tot += (pro * a[i].cheese);
	break;
}

最后的代码

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int M = 1e4 + 5;
int m, n;
double temp = 0, tot = 0;

struct room{
	int cat_food;
	int cheese;
}a[M];

bool cmp(room x, room y) {
	return double(x.cheese) / x.cat_food > double(y.cheese) / y.cat_food;
}

int main() {
	scanf("%d %d", &m, &n);
	for(int i = 1; i <= n; i ++) {
		scanf("%d %d", &a[i].cheese, &a[i].cat_food);
	}
	sort(a + 1, a + 1 + n, cmp);
	for(int i = 1; i <= n; i ++) {
		if(temp + a[i].cat_food > m) {
			double num = m - temp;
			double pro = num / a[i].cat_food;
			tot += (pro * a[i].cheese);
			break;
		}
		else {
			temp += a[i].cat_food;
			tot += a[i].cheese;
		}
	}
	printf("%.3lf", tot);
	return 0;
}