一、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
5 3
7 2
4 3
5 2
20 3
25 18
24 15
15 10
-1 -1
 
Sample Output
13.333
31.500

二、Solution

贪心问题，主要就是先排序

三、Code

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
/**
 * date:2017.11.14
 * author:孟小德
 * function:acm1099
 *  FatMouse' Trade
 */  



import java.util.*;  
import java.text.DecimalFormat;  

public class acm1009  
{  
    public static void main(String[] args)  
    {  
        Scanner input = new Scanner(System.in);  
        DecimalFormat df = new DecimalFormat("0.000");  

        int catf_num;  
        int room_num;  


        ArrayList<String> result = new ArrayList<String>();  
        while ((catf_num = input.nextInt()) != -1 && (room_num = input.nextInt()) != -1)  
        {  
            double[][] source = new double[room_num][2];  
            double[] persent = new double[room_num];  
            for (int i=0;i<room_num;i++)  
            {  
                source[i][0] = input.nextDouble();  
                source[i][1] = input.nextDouble();  
                persent[i] = source[i][0]/source[i][1];  
            }  


            sortArray(source,persent);  


            double getNum = 0.0;  
            for (int i=persent.length-1;i>=0;i--)  
            {  
                // int n = map.get(persent[i]);  
                if (source[i][1] <= catf_num)  
                {  
                    getNum += source[i][0];  
                    catf_num -= source[i][1];  
                }  
                else  
                {  
                    getNum += catf_num * persent[i];  
                    break;  
                }  
            }  

            System.out.printf("%.3f",getNum);  
            System.out.println();  

        }  


    }  

    //对输入的resource进行排序  
    public static void sortArray(int[][] source,double[] persent)  
    {  
        boolean flag = true;  
        Double temp;  
        int[] tempArray = new int[2];  
        for (int i = 0;i<persent.length && flag;i++)  
        {  
            flag = false;  
            for (int j = 0;j<persent.length-i-1;j++)  
            {  
                if (persent[j] > persent[j+1])  
                {  
                    temp = persent[j];  
                    persent[j] = persent[j+1];  
                    persent[j+1] = temp;  

                    tempArray[0] = source[j][0];  
                    tempArray[1] = source[j][1];  

                    source[j][0] = source[j+1][0];  
                    source[j][1] = source[j+1][1];  

                    source[j+1][0] = tempArray[0];  
                    source[j+1][1] = tempArray[1];  

                    flag = true;  
                }  
            }  
        }  
    }  


    static void sort(double[] a,double[][] c) {  
        int len = a.length;  
        int low = 0,high = len - 1;  
        quickSort(a,c, low, high);  
    }  

    static void quickSort(double[] a, double[][] c,int l ,int h){  
        if(l>=h){  
            return;  
        }  
        int low = l;  
        int high = h;  
        double k = a[low];  
        double k2 = c[low][0];  
        double k3 = c[low][1];  
        while(low< high){  
            //  
            while(high>low&&a[high]>=k){//寻找元素右边比其小的  
                high --;  
            }  
            a[low] = a[high];//进行交换，K指向high  
            c[low][0] = c[high][0];  
            c[low][1] = c[high][1];  
            while(low<high&&a[low]<=k){//寻找元素左边比其大的  
                low++;  
            }  
            a[high] = a[low];//进行交换，K指向low  
            c[high][0] = c[low][0];  
            c[high][1] = c[low][1];  
        }  
        a[low] = k;//将K赋给low  
        c[low][0] = k2;  
        c[low][1] = k3;  
        quickSort(a, c,l, low-1);  
        quickSort(a, c,low+1, h);  
    }  


}

最后更新： 2018年12月27日 19:08

原始链接： https://cwhong.top/2018/12/25/程序日记本/杭电acm1009-FatMouse'Trade/

赏
× Thank you~
打赏二维码