打印队列(Printer Queue)

Printer Queue

Time limit: 3.000 seconds

【分析】

       首先记录所求时间它在队列中的位置，用一个队列存储这些任务的优先级，同时也创建一个队列存储对应任务一开始的位置，那么当我们对前一个队列进行什么操作时，后一个队列也跟着做什么操作即可，就可以保证两个队列的对应关系——任务对应初始位置。进行模拟时，从第一个队列取出一个任务（同时第二个队列也是进行同样的操作），判断该任务是否可以打印（通过循环判断，队列后面的元素任务优先级有木有大于当前任务的优先级即可），如果可以打印就将所求打印时间加1，并且判断是否是我们所求时间的位置，如果是，则停止模拟，如果不是则继续以上操作；如果不可以进行打印就将刚才取出来的数重新加到队尾（两个队列均是这样操作）。

用java语言编写程序，代码如下：

import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner input = new Scanner(System.in);
    int t = input.nextInt();
    for(int i = 0; i < t; i++) {
      int n = input.nextInt();
      int pos = input.nextInt();
      
      Queue<Integer> q = new LinkedList<Integer>();
      Queue<Integer> qn = new LinkedList<Integer>();
      
      for(int j = 0; j < n; j++) {
        int temp = input.nextInt();
        q.add(temp);
        qn.add(j);
      }
      
      int time = 0;
      while(true) {
        int temp = q.poll();
        int num = qn.poll();
        if(goOnPrint(temp, q)) {
          time++;
          if(num == pos)
            break;
        }
        else {
          q.add(temp);
          qn.add(num);
        }
      }
      
      System.out.println(time);
    }
  }
  
  public static boolean goOnPrint(int t, Queue<Integer> q) {
    Iterator<Integer> iterator = q.iterator();
    while(iterator.hasNext()) {
      int v = iterator.next();
      if(v > t)
        return false;
    }
    
    return true;
  }
}