java - 协助菜鸟进行Java堆应用

Question

在过去的 4 个小时里，我一直在为这项成堆的学校作业而苦苦挣扎。我对它们的工作原理有基本的了解，但由于某种原因，我在实现这个问题的想法时遇到困难。我真的很感激一些反馈和提示，因为这似乎并没有我自己的努力......

问题如下:我们有一个由整数表示的“机器”数组。该整数表示机器制造产品所需的时间。我们还得到一个整数，表示我们想要制造的产品数量。任务是尽快制造给定数量的产品并返回所需的时间。

例如:我们有机器 [1, 2, 3, 4]，产品数量为 10。答案应该是 6，因为:

• 在时间 (0) 我们“启动机器”(什么也不做)
• 在时间 (1)，我们从机器 1 中获得第一个产品
• 在时间 (2)，我们从机器 1 和 2 获得两种产品，因此现在总共有 3 个产品
• 在时间 (3)，我们从机器 1 和 3 获得两个产品，加起来为 5
• 在时间 (4)，我们从机器 1、2 和 4 获得三种产品，总共 8 种
• 在时间 (5)，我们只从机器 1 中获得一种产品，因此现在有 9
• 在时间 (6)，我们从机器 1 获取最后一个产品，并返回当前时间 6

机器和产品的数量在1..10^5之间。数组中的整数(机器的速度)在 1..10^9 之间。

我已经设法为该问题制定了一个工作代码，但它没有通过所有测试，因为它不够快。现在我尝试了一些方法来提高它的效率，但这样做只能破坏整个事情或者让它变得更慢。例如，我尝试检查堆中机器的“速度”是否大于 currentTime，然后结束循环以节省一些时间，但所做的只是再次测试超时(不知道为什么)。

public static long shortestTime(int[] machines, int amount) {

    PriorityQueue<Machine> heap = new PriorityQueue<Machine>();
    for (int i = 0; i < machines.length; i++) {
        heap.add(new Machine(machines[i]));
    }

    int currentTime = 0;  //Indicates how many time units have been used so far

    int timeOfNextProduct = -1;  //Tells the time when the next product(s) will be ready

    int numberOfNextProducts = 0;  //Keeps count of how many products will be ready at the next possible time any product can be finished

    int products = 0;  //Keeps count of the total number of products manufactured

    while (products < amount) {

        //We raise the current time by one
        currentTime++;

        //We check the next possible time for a product to be ready
        if (timeOfNextProduct == -1) {
            ArrayList<Machine> polled = new ArrayList();
            int i = heap.size();
            for (int j = 0; j < i; j++) {
                if (j == 0) {
                    timeOfNextProduct = heap.peek().getManufactureSpeed() + currentTime - 1;
                }
                Machine machine = heap.poll();
                if (timeOfNextProduct % machine.getManufactureSpeed() == 0) {
                    numberOfNextProducts++;
                }
                polled.add(machine);
            }
            for (int j = 0; j < polled.size(); j++) {
                heap.add(polled.get(j));
            }
        }

        //If there are products ready at current time, we add them to the 
        //integer "products" and reset the value of "timeOfNextProduct"
        if (currentTime == timeOfNextProduct) {
            products += numberOfNextProducts;
            if (products >= amount) {
                return currentTime;
            }
            timeOfNextProduct = -1;
            numberOfNextProducts = 0;
        } else {
            //We jump straight to the next interesting time
            //(minus 1 since we add 1 to currentTime in the beginning of the loop
            currentTime = timeOfNextProduct - 1;
        }

    }

    return currentTime;

}

public static void main(String[] args) {
    System.out.println(shortestTime(new int[]{1, 2, 3, 4}, 10));  //Prints out 6
}

公共(public)类 Machine 实现 Comparable {

private int manufactureSpeed;

public Machine(int manufactureSpeed) {
    this.manufactureSpeed = manufactureSpeed;
}

public int getManufactureSpeed() {
    return manufactureSpeed;
}

@Override
public int compareTo(Machine t) {
    if (this.manufactureSpeed < t.manufactureSpeed) {
        return -1;
    }
    return 1;
}

}

Answer 1

您使用优先级队列的方式是问题的根源。

这里使用优先级队列的全部目的是了解机器何时完成生产。

因此，您应该通过给机器一种时间感来让机器知道它何时完成生产，然后根据机器何时生产出东西来创建比较函数。

这样你就可以从队列前面取出这次生产东西的机器，然后将它们放回后面。