杭电 ACM 1009 FatMouse' Trade

做完FatMouse' Trade， 发现这题其实有很多陷阱，一不小心就可能出错。其中有几个特殊的测试资料是这样的：

1. cat food 为 0 的情况；

2. j[i] 为 0 的情况；

3. f[i] 为 0 的情况；

呃……由于是第二次做，所以只记得这么多了。还是看看代码吧，我还不知道什么是贪心法，只是按照自己的思路做一遍，觉得由于它的测试数据量也不大（小于 1000），所以用平常的算法就可以了吧？

/* THE PROGRAM IS MADE BY PYY */

/*
        http://acm.hdu.edu.cn/showproblem.php?pid=1009
        FatMouse' Trade
        Begin : 16:00
        End   : 17:05

*/

/* Test data:
0 3
100 0
100 0
100 0

Answer 
300.000

*/

#include <iostream>
#include <stdio.h>
using namespace std;

struct Trade {
        int javaBean, food;
        double rate;
};

int main()
{
        const int max = 1001;
        int catFood, N;
        int i, j, f, maxIdx;
        double r, get;
        Trade record[max], tmp;
        while (cin >> catFood >> N && (catFood != -1) && (N != -1)) {
                i = get = 0;
                while (i < N) {
                        cin >> j >> f;
                        if (j == 0)
                                r = 0.0;
                        else if (f == 0)
                                r = static_cast<double>(max);
                        else
                                r = 1.0 * j/f;
                        record[i].javaBean = j;
                        record[i].food = f;
                        record[i].rate = r;
                        i++;
                }

                // sort
                for (j = 0; j < N - 1; j++) {
                        // the last one
                        maxIdx = N - 1;
                        for (f = j; f < N; f++) {
                                if (record[maxIdx].rate < record[f].rate)
                                        maxIdx = f;
                        }

                        // swap
                        tmp = record[j];
                        record[j] = record[maxIdx];
                        record[maxIdx] = tmp;
                }

                // mouse will get
                for (i = 0; i < N; i++) {
                        f = record[i].food;
                        j = record[i].javaBean;
                        if (catFood >= f) {
                                get += j;
                                catFood -= f;
                        } else {
                                r = 1.0 * catFood / f;
                                get += j * r;
                                catFood = 0;
                        }
                }
                printf("%0.3f/n", get);
        }

        return 0;
}