HDU 1009 FatMouse' Trade

忽然发现HDU上还有一道残留的没A过去的水题，那是当年年轻的我太菜了(现在依然很菜)。

简单的贪心，因为老鼠可以用猫粮等比例的换取每个房间里的Java豆，所以我们先换汇率高的，再换汇率低的。

 1 //#define LOCAL
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 const int maxn = 1000 + 10;
 8 struct Trade
 9 {
10     double f, j;
11 }trade[maxn];
12 
13 bool cmp(Trade a, Trade b)
14 {
15     return (a.j*b.f > a.f*b.j);
16 }
17 
18 double ans, tot;
19 int n;
20 
21 int main(void)
22 {
23     #ifdef LOCAL
24         freopen("1009in.txt", "r", stdin);
25     #endif
26 
27     while(scanf("%lf%d", &tot, &n) == 2)
28     {
29         if(n == -1)    break;
30         for(int i = 0; i < n; ++i)
31             scanf("%lf%lf", &trade[i].j, &trade[i].f);
32         sort(trade, trade + n, cmp);
33         int i = 0;
34         ans = 0;
35         while(tot > 0 && i < n)
36         {
37             if(tot >= trade[i].f)
38             {
39                 ans += trade[i].j;
40                 tot -= trade[i++].f;
41             }
42             else
43             {
44                 ans += tot * trade[i].j / trade[i].f;
45                 tot = 0;
46             }
47         }
48         printf("%.3lf
", ans);
49     }
50     return 0;
51 }

代码君