java - USACO 培训 : Mixing Milk fails on the last Case

Question

这是混合牛奶问题

Merry Milk Makers 公司从农民那里购买牛奶，将其包装成极具吸引力的 1 瓶和 2 瓶装，然后将这些牛奶卖给杂货店，这样我们每个人都可以享用美味的麦片和牛奶来开始新的一天。

由于牛奶包装是一项很难赚钱的行业，因此保持尽可能低的成本非常重要。帮助 Merry Milk Makers 以最便宜的方式购买农民的牛奶。 MMM 公司拥有一个非常有才华的营销部门，并且准确地知道他们每天需要为客户包装多少牛奶。

该公司与几家农场主签订了契约(Contract)，他们可以从这些农场主那里购买牛奶，并且每个农场主都有(可能)不同的价格向包装厂出售牛奶。当然，一群奶牛每天只能产那么多牛奶，所以农民们已经知道他们有多少牛奶可用。

每天，Merry Milk Makers 可以从每个农民那里购买整数单位的牛奶，这个数字总是小于或等于农民的限制(并且可能是那个农民的全部产品，没有生产，或两者之间的任何整数)。

给定:

The Merry Milk Makers 的每日牛奶需求量 每个农民每单位牛奶的成本 每个农民可获得的牛奶量 计算 Merry Milk Makers 必须花费的最低金额才能满足他们对牛奶的日常需求。

第 1 行:两个整数，N 和 M。

第一个值 N (0 <= N <= 2,000,000) 是 Merry Milk Makers 每天需要的牛奶量。 第二个 M，(0 <= M <= 5,000)是他们可以从农民那里购买的数量。

第 2 行到 M+1:

接下来的 M 行每行包含两个整数:Pi 和 Ai。 Pi (0 <= Pi <= 1,000) 是农民 i 收取的美分价格。 Ai (0 <= Ai <= 2,000,000) 是农夫 i 每天可以卖给 Merry Milk Makers 的牛奶量。

---

我的解决方案:

我的解决方案是将农民的牛奶价格和他们拥有的牛奶数量存储在 HashMap 中。只要还有牛奶要买，我就会将 HashMap 中的最低价 * 最低价牛奶的数量添加到成本中，因为我对 ArrayList 储存牛奶的成本。因为购买的牛奶可能比需要的多，所以我有一个 if 语句 检查如果购买的牛奶比需要的多，就会减去额外的费用。然后我从 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();
    }
}

Answer 1

我敢肯定，您没有正确考虑当多个奶农以相同价格出售牛奶时会发生什么。

您使用 HashMap 的方式意味着您将覆盖以前农民的值。