1009 FatMouse' Trade

发表于 更新于 分类于
FatMouse' Trade 简单贪心算法

Problem Description

FatMouse prepared M pounds of cat food, ready to trade with the cats guarding the warehouse containing his favorite food, JavaBean.
The warehouse has N rooms. The i-th room contains J[i] pounds of JavaBeans and requires F[i] pounds of cat food. FatMouse does not have to trade for all the JavaBeans in the room, instead, he may get J[i]* a% pounds of JavaBeans if he pays F[i]* a% pounds of cat food. Here a is a real number. Now he is assigning this homework to you: tell him the maximum amount of JavaBeans he can obtain.

Input

The input consists of multiple test cases. Each test case begins with a line containing two non-negative integers M and N. Then N lines follow, each contains two non-negative integers J[i] and F[i] respectively. The last test case is followed by two -1’s. All integers are not greater than 1000.

Output

For each test case, print in a single line a real number accurate up to 3 decimal places, which is the maximum amount of JavaBeans that FatMouse can obtain.

Sample Input

1
2
3
4
5
6
7
8
9
5 3
7 2
4 3
5 2
20 3
25 18
24 15
15 10
-1 -1

Sample Output

1
2
13.333
31.500

Suggest Answer

很简单的一题贪心,注意输出就好了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
import java.util.*;

class Trade {
    double a;
    double b;
    double c;

    Trade(double a, double b, double c) {
        this.a = a;
        this.b = b;
        this.c = c;
    }
}

class myComparator implements Comparator<Trade> {
    @Override
    public int compare(Trade o1, Trade o2) {
        if (o1.c < o2.c) {
            return 1;
        } else if (o1.c > o2.c) {
            return -1;
        } else {
            return 0;
        }
    }
}

class _1009 {
    public static void main(String[] args) {
        int M = 0, N = 0;
        Scanner input = new Scanner(System.in);
        M = input.nextInt();
        N = input.nextInt();
        while (M != -1 && N != -1) {
            double sum = 0.0;
            Trade[] trades = new Trade[N];
            myComparator comparator = new myComparator();
            for (int i = 0; i < N; i++) {
                double a = input.nextDouble();
                double b = input.nextDouble();
                double c = a / b;
                trades[i] = new Trade(a, b, c);
            }
            Arrays.sort(trades, 0, N, comparator);
            for (int i = 0; i < N; i++) {
                if (M > trades[i].b) {
                    sum += trades[i].a;
                    M -= trades[i].b;
                } else {
                    sum += M * trades[i].c;
                    break;
                }
            }
            System.out.printf("%.3f\n", sum);
            M = input.nextInt();
            N = input.nextInt();
        }
        input.close();
    }
}