本文主要是介绍hdoj 1009 FatMouse' Trade 【贪心】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=1009
思路:先求出每一个仓库的交换价值率（就是一个F能交换多少J），然后按照交换率排序，依次判断相加就可以了
代码：
#include<cstdio>
#include<algorithm>
using std::sort;
typedef struct{
double j, f;
double rat;
}str;
str s[1005];
int cmp(str a, str b)
{
return a.rat > b.rat;
}
int main()
{
double m;
int i, j, n;
while(scanf("%lf%d", &m, &n), n != -1&&m !=-1){
for(i = 0; i < n; i ++){
scanf("%lf%lf", &s[i].j, &s[i].f);
s[i].rat = s[i].j/s[i].f; //求交换价值率
//printf("%lf %lf %lf\n", s[i].j, s[i].f, s[i].rat);
}
sort(s, s+n, cmp);
double sum = 0;
for(i = 0; i < n; i ++){
if(m>=s[i].f){ //判断能不能全部交换
sum+=s[i].j;
//printf("%lf,,", sum);
m -= s[i].f;
}
else{
sum += s[i].rat*m;
m-=m;
break;
}
}
printf("%.3lf\n", sum);
}
return 0;
}
这篇关于hdoj 1009 FatMouse' Trade 【贪心】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
