HDOJ 1009 FatMouse' Trade 贪心算法greedy so easy!
看题：http://acm.hdu.edu.cn/showproblem.php?pid=1009
代码：
#include<iostream>#include<string>#include <cstdio>#include <cmath>#include<vector>#include<algorithm>#include<sstream>#include<cstdlib>#include<iomanip>using namespace std;struct node{double j,p;double jp;};bool comp(node a,node b){return a.jp>b.jp;}int main(){int m,n;vector<node> buf;node tmp;while(cin>>m>>n){if(m==-1&&n==-1)break;for(int i=0;i<n;i++){cin>>tmp.j>>tmp.p;tmp.jp=tmp.j/tmp.p;buf.push_back(tmp);}sort(buf.begin(),buf.end(),comp);double sum=0;for(vector<node>::size_type i=0;i!=buf.size()&&m>0;i++){tmp=buf[i];if(m>=tmp.p){sum+=tmp.j;m-=tmp.p;}else {sum+=tmp.jp*m;m=0;}}cout<<fixed<<setprecision(3)<<sum<<endl;buf.clear();}return 0;}