一 问题描述

在计算机学生会里只有一台打印机，但是有很多文件需要打印，因此打印任务不可避免地需要等待。有些打印任务比较急，有些不那么急，所以每个任务都有一个 1~9 的优先级，优先级越高表示任务越急。

打印机的运转方式：首先从打印队列里取出一个任务J，如果队列中有比任务J更急的任务，则直接把J放到打印队列尾部，否则打印任务J（此时不会把它放回打印队列）。输入打印队列中各个任务的优先级以及你的任务在队列中的位置（队首位置为0），输出该任务完成的时刻。所有任务都需要1分钟打印。例如，打印队列为{1,1,9,1,1,1}，目前处于队首的任务最终完成时刻为5.

输入

第1行为测试用例数T，每个测试用例的第1行都包括n和m，其中n为打印任务数量，m为你的任务序号（从0开始编号）。接下来为n个数，为n个打印任务的优先级。

输出

对于每个测试用例，都单行输出你的作业打印完成的分钟数。

输入样例
3

1 0

5

4 2

1 2 3 4

6 0

1 1 9 1 1 1

输出样例

1

2

5

二 思路

本问题需要用到一个队列存储打印任务，还需要知道当前队列中优先级最高是多少。首先从队首取出一个任务J，如果J的优先级不低于队列中的最高优先级，则直接打印，否则将任务J放入队尾。怎么知道当前队列中的最高优先级呢？最简单的方法就是按优先级非递增排序。

三 算法设计

1 读入 T，表示 T 组测试用例。

2 读入 n、m，表示打印的任务个数和你要打印的任务编号。

3 读入优先级序列，将其存储在 a[]、b[] 两个数组中，并将优先级序列的下标依次（从 0 开始）放入队列 q。

4 b[] 数组非递增排序，w=0，k=0，w 为b的下标，k 用来计数已打印了多少个任务。

5 如果队列 q 非空，则取出队头下标 t，它的优先级为 a[t],max=b[w],如果a[t]<max,则 t 出队后被放入队尾，否则将 t 与 m 进行比较，如果相等，则输出k，跳出循环；如果不相等，则出队，k,w++。

6 在 T 组数据处理完毕后结束。

四 图解

1 以下面的输入样例为例，n=4，m=2，即共有 4 个打印任务，你的打印任务为2.
4 2

1 2 3 4

2 读入优先级序列，将其存储在 a[]、b[] 两个数组中，并将优先级序列下标依次（从0开始）放入队列 q，如下图所示。

3 b[] 数组非递增排序，初始化 w=0，k=0，如下图所示。

4 取队头 t=0，其优先级a[0]=1,max=b[0]=4,a[0]<max,则将 t 出队并放入队尾。

5 取队头 t=1，其优先级a[1]=2,max=b[0]=4,a[1]<max,则将 t 出队并放入队尾。

6 取队头 t=2，其优先级a[2]=3,max=b[0]=4,a[2]<max,则将 t 出队并放入队尾。

7 取队头 t=3，其优先级a[3]=4,max=b[0]=4,a[3]=max,可以打印该任务。但 t !=m,不是你打印的任务，出队，k++，w++，此时 w=1，k=1，队列如下图所示。

8 取队头 t=0，其优先级a[0]=1,max=b[1]=3,a[0]<max,则将 t 出队并放入队尾。

9 取队头 t=1，其优先级a[1]=2,max=b[1]=3,a[1]<max,则将 t 出队并放入队尾。

10 取队头 t=2，其优先级a[2]=3,max=b[1]=3,a[1]=max,可以打印该任务。t=m，是你打的任务，输出++k，此时k=2，输出2，表示打印的任务分钟数为2。

五 实现

package vector;

import java.util.*;

public class PrintTask {
    public static void main(String[] args) {
        int T;
        int n;
        int m;
        Scanner scanner = new Scanner(System.in);
        T = scanner.nextInt();
        for (int i = 0; i < T; i++) {
            Vector<Integer> a = new Vector<>();
            Vector<Integer> b = new Vector<>();
            LinkedList<Integer> q = new LinkedList<>();
            int k = 0;
            int x;
            n = scanner.nextInt();
            m = scanner.nextInt();
            for (int j = 0; j < n; j++) {
                x = scanner.nextInt();
                a.addElement(x);
                b.addElement(x);
                q.add(j);
            }
            Collections.sort(b);
            Collections.reverse(b);
            int w = 0;
            int max ;
            while (!q.isEmpty()) {
                max = b.get(w);
                int t = q.getFirst();
                if (a.get(t) < max) {
                    q.poll();
                    q.offer(t);
                } else {
                    if (t == m) {
                        System.out.println(++k);
                        break;
                    } else {
                        q.poll();
                        k++;
                        w++;
                    }
                }
            }
        }
    }
}

六 测试

绿色为输入，白色为输出