使用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之间。

我已经设法解决了这个问题的工作代码，但它没有通过所有的测试，因为它不够快。现在我已经尝试过让它更有效率，但是这样做我只能设法打破整个事情，或者让它变得更慢。例如，我试着检查堆中的机器“速度”是否大于当前时间，然后结束循环以节省一些时间，但所做的只是使另一个测试时间结束（不知道为什么）。

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 
} 

公共类机实现可比{

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

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

在这里使用优先队列的关键在于知道机器何时完成生产。

所以你应该让机器知道什么时候完成生产，然后根据机器什么时候生产某些东西来做比较功能。

这样，您可以从队列的前面拿出产生某些东西的机器，并将它们放回到后面。