Jobdu-21-FatMouse's house

Posted on | In

Question

题目描述：
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.

输入：
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.

输出：
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.

样例输入：
5 3
7 2
4 3
5 2
20 3
25 18
24 15
15 10
-1 -1

样例输出：
13.333
31.500

Answer

Using array
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
import java.util.Scanner;
public class MyClass{
    public static void main(String[] args) {
        double m;
        int n;
        Scanner sc  = new Scanner(System.in);
        while((m=sc.nextInt())!=-1 && (n=sc.nextInt())!=-1){
            double j[] = new double[n];  //j pound JavaBean
            double f[] = new double[n];  //f pound cat food
            double r[] = new double[n];  //ratio of JavaBean and cat food
            int idx = n - 1;  //index of product
            double res = 0;
            for(int i=0;i<n;i++){
                j[i] = sc.nextDouble();
                f[i] = sc.nextDouble();
                r[i] = j[i]/f[i];
            }
            sort(r, j, f);
            while(m > 0 && idx > -1){
                if(m >= f[idx]){ // buy thea whole
                    m -= f[idx];
                    res += j[idx];
                }
                else{ // only could buy the part
                    res += j[idx] * m / f[idx];
                    m = 0;
                }
                idx--;
            }
            System.out.printf("%.3f", res);
            System.out.println();
        }
    }
    public static void sort(double[] r, double[] j, double[] f){
        int low = 0;
        int high = r.length-1;
        quicksort(r, j, f, low, high);
    }
    public static void quicksort(double[] r, double[] j, double[] f, int l, int h){
        if(l >= h)
            return ;
        int low = l, high = h;
        double temp_r = r[low];
        double temp_j = j[low];
        double temp_f = f[low];
        while(low < high){
            while(low < high && r[high] >= temp_r)
                high --;
            r[low] = r[high];
            j[low] = j[high];
            f[low] = f[high];
            while(low < high && r[low] <= temp_r)
                low ++;
            r[high] = r[low];
            j[high] = j[low];
            f[high] = f[low];
        }
        r[low] = temp_r;
        j[low] = temp_j;
        f[low] = temp_f;
        quicksort(r, j, f, l, low);
        quicksort(r, j, f, high+1, h);
    }
}
Using comparable
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
import java.util.Scanner;
import java.util.Arrays;
public class MyClass implements Comparable<MyClass>{
    public int j;
    public int f;
    public double r;
    
    public MyClass(int j, int f, double r){
        super();
        this.j = j;
        this.f = f;
        this.r = r;
    }
    public int compareTo(MyClass obj){
        if(this.r > obj.r)
            return -1;
        else if(this.r < obj.r)
            return 1;
        return 0;
    }
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            int m = in.nextInt();
            int n = in.nextInt();
            if(m == -1)
                break;
            MyClass[] goods = new MyClass[n];
            for(int i = 0; i < n; i++){
                int j = in.nextInt();
                int f = in.nextInt();
                goods[i] = new MyClass(j, f, (double)j / f);
            }
            Arrays.sort(goods);
            double res = 0;
            int idx = 0;
            while(m > 0 && idx < n){
                if(goods[idx].f <= m){
                    res += goods[idx].j;
                    m -= goods[idx].f;
                }
                else{
                    res += m * goods[idx].r;
                    m = 0;
                }
                idx ++;
            }
            System.out.printf("%.3f%n", res);
        }
        
    }
}