协助菜鸟 Java 堆应用

Question

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

问题如下：我们有一个 "machines" 的数组，用整数表示。整数表示机器制造产品所花费的时间。我们还得到一个整数，表示我们要制造的产品数量。任务是尽快制造给定数量的产品，并 return 花费的时间。

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

在时间 (0) 我们 "start up the machines"（什么都不做）
在时间 (1) 我们从机器 1 中得到第一个产品
在时间 (2) 我们从机器 1 和 2 得到两个产品，所以我们现在总共有 3 个
在时间 (3) 我们从机器 1 和 3 得到两个产品，加起来是 5
在时间(4)我们得到三个产品，分别来自机器1、2、4，总共8个
在时间 (5) 我们只从机器 1 得到一个产品，所以我们现在有 9
在时间 (6) 我们从机器 1 得到最后一个产品，return 当前时间是 6

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

之间

我已经设法为这个问题制定了一个工作代码，但它没有通过所有测试，因为它不够快。现在我已经尝试了一些方法来提高它的效率，但这样做只会破坏整个事情或者让它变得更慢。例如，我尝试检查堆中的机器 "speed" 是否大于 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 class 机具相当{

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

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

这里使用优先级队列的全部意义在于知道机器何时完成生产。

所以你应该让机器知道它什么时候完成生产，给它一个时间感，然后根据机器何时生产某些东西来制作比较功能。

这样你就可以把这次生产的机器从队列的前面拿出来，然后放回后面。

协助菜鸟 Java 堆应用

Assist a rookie with Java heap application

java

heap