hdoj 1009 FatMouse' Trade

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1009

解题思路：按单位 cat food 所能换取的 JavaBeans 量（即 J[i]/F[i] ）从大到小排序，优先选择比值大的进行交换，直到消耗完 cat food 。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<iomanip>
 4 using namespace std;
 5 
 6 struct Trade{
 7     int J,F;
 8     double C;
 9     bool operator <(const Trade &t) const{
10         return C>t.C;
11     }
12 }T[1005];
13 
14 int main(){
15     int m,n,i;
16     while(cin>>m>>n){
17         if(m==-1 && n==-1) break;
18         for(i=0;i<n;i++){
19             cin>>T[i].J>>T[i].F;
20             T[i].C=(T[i].J+0.0)/T[i].F;
21         }
22         sort(T,T+n);
23         double max=0;
24         for(i=0;i<n && m>0;i++){
25             if(m>=T[i].F){
26                 max+=T[i].J;
27                 m-=T[i].F;
28             }
29             else{
30                 max+=(m*T[i].J+0.0)/T[i].F;
31                 m=0;
32             }
33         }
34         cout<<fixed<<setprecision(3)<<max<<endl;
35     }
36     return 0;
37 }