PAT乙级-1020 月饼(Pat grade B-1020 moon cake)

月饼是中国人在中秋佳节时吃的一种传统食品,不同地区有许多不同风味的月饼。现给定所有种类月饼的库存量、总售价、以及市场的最大需求量,请你计算可以获得的最大收益是多少。

注意:销售时允许取出一部分库存。样例给出的情形是这样的:假如我们有 3 种月饼,其库存量分别为 18、15、10 万吨,总售价分别为 75、72、45 亿元。如果市场的最大需求量只有 20 万吨,那么我们最大收益策略应该是卖出全部 15 万吨第 2 种月饼、以及 5 万吨第 3 种月饼,获得 72 + 45/2 = 94.5(亿元)。

输入格式:

每个输入包含一个测试用例。每个测试用例先给出一个不超过 1000 的正整数 N 表示月饼的种类数、以及不超过 500(以万吨为单位)的正整数 D 表示市场最大需求量。随后一行给出 N 个正数表示每种月饼的库存量(以万吨为单位);最后一行给出 N 个正数表示每种月饼的总售价(以亿元为单位)。数字间以空格分隔。

输出格式:

对每组测试用例,在一行中输出最大收益,以亿元为单位并精确到小数点后 2 位。

输入样例:

3 20
18 15 10
75 72 45
结尾无空行

输出样例:

94.50
结尾无空行

代码:

代码来自 https://blog.csdn.net/huanglei305/article/details/105137256

参考 https://blog.csdn.net/fluetty/article/details/106448979

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
    static class Cake implements Comparable<Cake>{
        double amount;
        double price;
        double value;
        
        public Cake(double amount, double price, double value) {
           this.amount = amount;
           this.price = price;
           this.value = value;
        }

        @Override
        public int compareTo(Cake o) {
            return value > o.value ? -1 : 1;
        }
        
    }
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] in = br.readLine().split(" ");
        int n = Integer.parseInt(in[0]);
        int d = Integer.parseInt(in[1]);

        ArrayList<Cake> list = new ArrayList<Cake>();
        String[] w = br.readLine().split(" "), pr = br.readLine().split(" ");
        
        for (int i = 0; i < n; i++) {
            double m = Double.parseDouble(w[i]);
            double p = Double.parseDouble(pr[i]);
            double value = p/m;
            list.add(new Cake(m, p, value));
        }
        
        Collections.sort(list);

        double sum = 0;
        for (int i = 0; i < n; i++) {
            if (d - list.get(i).amount >= 0) {
                sum += list.get(i).price;
                d -= list.get(i).amount;
            } else {
                sum += list.get(i).value * d;
                break;
            }
        }
        System.out.println(String.format("%.2f", sum));
    }
}

————————

Moon cake is a traditional food eaten by Chinese people during the Mid Autumn Festival. There are many moon cakes with different flavors in different regions. Given the inventory, total selling price and maximum market demand of all kinds of moon cakes, please calculate the maximum profit you can get.

Note: it is allowed to take out part of the inventory during sales. The example shows that if we have three kinds of moon cakes, the inventory is 180000 tons, 150000 tons and 100000 tons respectively, and the total selling price is 7.5 billion yuan, 7.2 billion yuan and 4.5 billion yuan respectively. If the maximum demand of the market is only 200000 tons, our maximum revenue strategy should be to sell all 150000 tons of the second kind of moon cake and 50000 tons of the third kind of moon cake, and obtain 72 + 45 / 2 = 9.45 billion yuan.

Input format:

Each input contains a test case. Each test case first gives a positive integer no more than 1000, n represents the number of types of moon cakes, and a positive integer no more than 5 (in 10000 tons) d represents the maximum market demand. The next line gives n positive numbers to represent the inventory of each kind of moon cake (in 10000 tons); The last line gives n positive numbers to represent the total selling price of each kind of moon cake (in billion yuan). Numbers are separated by spaces.

Output format:

For each group of test cases, the maximum benefit is output in one line, with 100 million yuan as the unit and accurate to 2 decimal places.

Input example:

3 20
18 15 10
75 72 45
结尾无空行

Output example:

94.50
结尾无空行

code:

代码来自 https://blog.csdn.net/huanglei305/article/details/105137256

参考 https://blog.csdn.net/fluetty/article/details/106448979

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
    static class Cake implements Comparable<Cake>{
        double amount;
        double price;
        double value;
        
        public Cake(double amount, double price, double value) {
           this.amount = amount;
           this.price = price;
           this.value = value;
        }

        @Override
        public int compareTo(Cake o) {
            return value > o.value ? -1 : 1;
        }
        
    }
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] in = br.readLine().split(" ");
        int n = Integer.parseInt(in[0]);
        int d = Integer.parseInt(in[1]);

        ArrayList<Cake> list = new ArrayList<Cake>();
        String[] w = br.readLine().split(" "), pr = br.readLine().split(" ");
        
        for (int i = 0; i < n; i++) {
            double m = Double.parseDouble(w[i]);
            double p = Double.parseDouble(pr[i]);
            double value = p/m;
            list.add(new Cake(m, p, value));
        }
        
        Collections.sort(list);

        double sum = 0;
        for (int i = 0; i < n; i++) {
            if (d - list.get(i).amount >= 0) {
                sum += list.get(i).price;
                d -= list.get(i).amount;
            } else {
                sum += list.get(i).value * d;
                break;
            }
        }
        System.out.println(String.format("%.2f", sum));
    }
}