打印队列问题

x33g5p2x  于2022-04-10 转载在 其他  
字(2.1k)|赞(0)|评价(0)|浏览(231)

一 问题描述

在计算机学生会里只有一台打印机,但是有很多文件需要打印,因此打印任务不可避免地需要等待。有些打印任务比较急,有些不那么急,所以每个任务都有一个 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++;
                    }
                }
            }
        }
    }
}

六 测试

绿色为输入,白色为输出

相关文章

微信公众号

最新文章

更多