欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

老鼠与猫的交易

程序员文章站 2022-06-23 09:36:56
因为之前一直想做新题(摸鱼),所以今天才写题解题目描述:有一只老鼠很喜欢奶酪,但是奶酪被分别放在N个房间里,而且这些房间都有一只猫咪看守,现在它准备和猫咪们做个交易。它有M磅的猫食,想用这M磅猫食换取奶酪。在猫咪看守的每一个房间里有奶酪 J[i] 磅,同时猫咪需要 F[i] 磅的食物,如果老鼠给猫咪 F[i] (a)% 的猫食,那么它就可以得到J[i] (a)%的奶酪。现在已知每只猫咪对猫食的需求量和每个房间的奶酪数,那老鼠怎样才能换得最多的奶酪呢?输入第一行输入两个正整数M和N(M和N不大于10...

因为之前一直想做新题(摸鱼),所以今天才写题解


题目描述:

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

输入

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

输出

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

数据范围:

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


思路:

选择 奶酪/猫食 尽量大的(选择性价比高的)

代码:
#include <cstdio>
#include <algorithm>
using namespace std;

int n, m;
struct jgt{
	int a, b;
	double c;
};
bool cmp(jgt x, jgt y){
	return x.c > y.c;
}
jgt mouse[10005];
double sum;
int main() {
	scanf("%d %d", &m, &n);
	for(int i = 1; i <= n; i ++){
		scanf("%d %d", &mouse[i].a, &mouse[i].b);
		mouse[i].c = mouse[i].a * 1.0/ mouse[i].b;
	}
	sort(mouse + 1, mouse + n + 1, cmp);
	int t = 1;
	for(int i = 1; i <= n; i ++){
		if(m >= mouse[i].b){
			sum += mouse[i].a;
			m -= mouse[i].b;
		}
		else{
			sum += (m * 1.0 / mouse[i].b) * mouse[i].a; 
			break;
		}
	}
	printf("%.3lf", sum);
	return 0;
} 

本文地址:https://blog.csdn.net/DYNHlalalalala/article/details/107324474