hodj 1009 FatMouse' Trade--贪心算法

本文主要是介绍hodj 1009 FatMouse' Trade--贪心算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

  整体思路：整体思路就是以 JavaBean/CatFood比为基准，比值大的房间优先。使用结构体排序，结构体排序。

#include <iostream>
#include <algorithm>
#include <string>
#include <map>
#include <stdio.h>
using namespace std;struct trade{double a;//JavaBeandouble b;//CatFooddouble c;
}fj[1000];int compare(trade a,trade b){return a.c > b.c; //运用结构体变量存储
}int main() {int m,n;double j,f,sum;while(1){sum =0;cin >> m;cin >> n;if(m== -1 && n== -1){break;}for(int i=0;i<n;i++){cin >> j;cin >> f;fj[i].a=j;fj[i].b=f;fj[i].c=j/f;}sort(fj,fj+n,compare);//用结构体中的c变量的大小进行排序，注意这个是从大到小进行!for(int j=0; j<n; j++){if(m - fj[j].b > 0.001){sum+=fj[j].a;m-=fj[j].b;}//当m大于整体b时else{sum+=m*fj[j].a/fj[j].b;break;}}printf("%.3lf\n",sum);}return 0;
}

 

 

这篇关于hodj 1009 FatMouse' Trade--贪心算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---