java - USACO培训:在最后一个案例中混合牛奶失败

这是混合牛奶问题。
快乐牛奶制造商公司从农民那里购买牛奶，将其包装成有吸引力的1和2个单位的瓶子，然后把牛奶卖给杂货店，这样我们就可以开始一天的美味谷物和牛奶了。
由于牛奶包装是一个很难赚钱的行业，所以尽量降低成本是很重要的。帮助快乐的牛奶制造商以最便宜的方式购买农民的牛奶。mmm公司有一个非常有才华的市场营销部门，并且非常清楚他们每天需要多少牛奶来为客户包装。
该公司与几个农民签订了合同，他们可以从这些农民那里购买牛奶，每个农民（可能）向包装厂出售牛奶的价格不同。当然，一个牛群每天只能产那么多牛奶，所以农民们已经知道他们将有多少牛奶。
每天，快乐的牛奶制造者可以从每个农民那里购买整数单位的牛奶，这个数字总是小于或等于农民的限制（并且可能是来自该农民的全部生产，而不是生产，或者两者之间的任何整数）。
鉴于：
快乐奶业者每日所需的牛奶
每位农民每单位牛奶的成本
每个农民的奶量
计算快乐牛奶制造商为满足他们每天的牛奶需求而必须花费的最低金额。
第1行：两个整数，N和M。
第一个值n（0第二个，M，（0第2至M+1行：
接下来的m行各包含两个整数：pi和ai。
pi（0ai（0我的解决方案：
我的解决办法是把农民的牛奶价格和牛奶数量存储在HashMap中。只要还有牛奶要买，我就把最低价格*最低价格牛奶的数量从HashMap加到成本中，因为我把存储牛奶成本的ArrayList排序因为有可能购买的牛奶比需要的多，所以我有一个if statement检查，如果购买的牛奶比需要的多，额外的成本就会被减去。然后从ArrayList中删除最低价格
代码：
这些代码适用于所有的测试用例，除了上一个测试用例之外，其中有太多的数据要放入问题中，所以我将它链接到一个Google文档。
输入和输出：https://docs.google.com/document/d/10I3b0z17kP_LZzD2lBlH-Igoe6NPybZleD9tNYonqSQ/edit?usp=sharing

/*
ID: henry.d2
LANG: JAVA
TASK: milk
*/

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class milk
{
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new FileReader("milk.in"));

        String[] components = br.readLine().split(" ");

        int n = Integer.parseInt(components[0]); // Get the amount of milk that Merry Milk Makers wants per day (N)
        int m = Integer.parseInt(components[1]); // Get the number of farmers that they may buy from (M)

        Map<Integer, Integer> farmerAndPrice = new HashMap<Integer, Integer>(); // HashMap that stores the prices of milk and quantities
        List<Integer> prices = new ArrayList<Integer>(); // ArrayList that stores the prices for milk

        // Read in P(i) (The price in cents that farmer i charges) and A(i) (The amount of milk that farmer i can send to MMM per day)
        for (int i = 0; i < m; i++)
        {
            String[] pAndA = br.readLine().split(" ");

            int Pi = Integer.parseInt(pAndA[0]);
            int Ai = Integer.parseInt(pAndA[1]);

            farmerAndPrice.put(Pi, Ai); // Add price and quantity to HashMap
            prices.add(Pi); // Add price to ArrayList
        }

        Collections.sort(prices);

        int milkToBuy = 0;
        int cost = 0;

        while (milkToBuy < n) // The farmers still have milk to buy from
        {
            cost += farmerAndPrice.get(prices.get(0)) * prices.get(0);
            milkToBuy += farmerAndPrice.get(prices.get(0));

            if (milkToBuy > n) // If we buy more milk than we need
            {
                cost -= (milkToBuy - n) * prices.get(0);
            }

            System.out.println(prices.toString());

            prices.remove(0);
        }

        File file = new File("milk.out"); // Output to milk.out
        PrintWriter printWriter = new PrintWriter(file);

        printWriter.println(cost);

        printWriter.close();
    }
}

最佳答案

我很有信心，你没有正确地考虑到当多个农民以同样的价格出售牛奶时会发生什么。
使用散列映射的方式意味着您将覆盖以前农民的值。

关于java - USACO培训:在最后一个案例中混合牛奶失败，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/35494068/