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

贪心之老鼠与猫的交易(详细分析)

程序员文章站 2022-07-12 12:18:22
...

题目描述

有一只老鼠很喜欢奶酪,但是奶酪被分别放在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

算法分析

这一题很明显为贪心算法,但因为a不定,所以最为困难的就是a%。而这时候,易发现当a[i].j很小而a[i].f很大时,这是我们最想要的情况,所以简洁来说就是当a[i].f/a[i].j最大时,是我们最佳贪心策略

代码

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=100005;
struct cat{
	int f,j;
	double tot;//f/j的值
}a[M];
bool cmp(cat x,cat y){//将tot排序处理
	if(x.tot<y.tot)
	return false;
	return true;
}
int main(){
	int m,n;
	scanf("%d %d",&m,&n);
	for(int i=1;i<=n;i++){
		scanf("%d %d",&a[i].f,&a[i].j);
		a[i].tot=a[i].f*1.0/a[i].j;
	}
	sort(a+1,a+1+n,cmp);
	double sum=0;
	for(int i=1;i<=n;i++){
		if(m>=a[i].j){
			m-=a[i].j,sum+=a[i].f;
		}
		else{
			double id=m*1.0/a[i].j;
			sum+=a[i].f*1.0*id;
			break;//最后处理剩下的m
		}
	}
	printf("%.3lf",sum);
} 
相关标签: 贪心 贪心算法