天天看點

杭電ACM第1009題——FatMouse' Trade

#include <iostream>
#include<iomanip>
#include<algorithm>
using namespace std;
typedef struct thing{
	int value;
	int weight;
	double vw;
};

bool cmp(thing a,thing b){
	return a.vw>b.vw;
}

int main() {
	int m,n,i;
	double sum;
	while(cin>>m>>n&&m!=-1&&n!=-1) {
		thing *p=new thing[n];
		for(i=0;i<n;i++){
			cin>>p[i].value>>p[i].weight;
			p[i].vw=p[i].value*1.0/p[i].weight;
		}
		
		sort(p,p+n,cmp);
		for(sum=0,i=0;i<n;i++){
			if(m>p[i].weight){
				sum+=p[i].value;
				m-=p[i].weight; 
			} 
			else{
				sum+=p[i].vw*m;
				break;
			}
		}
		cout.setf(ios::fixed);
		cout<<setprecision(3)<<sum<<endl;
	}
	return 0;
}
           

繼續閱讀