华为OD机试 - 打印任务排序 - 队列（Java 2024 C卷 100分）

在这里插入图片描述

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（A卷+B卷+C卷）》。

刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

某个打印机根据打印队列执行打印任务。打印任务分为九个优先级，分别用数字1-9表示，数字越大优先级越高。打印机每次从队列头部取出第一个任务A，然后检查队列余下任务中有没有比A优先级更高的任务，如果有比A优先级高的任务，则将任务A放到队列尾部，否则就执行任务A的打印。

请编写一个程序，根据输入的打印队列，输出实际的打印顺序。

二、输入描述

输入一行，为每个任务的优先级，优先级之间用逗号隔开，优先级取值范围是1~9。

三、输出描述

输出一行，为每个任务的打印顺序，打印顺序从0开始，用逗号隔开。

1、输入

9,3,5

2、输出

0,2,1

3、说明

队列头部任务的优先级为9，优先级最高，序号为0；
然后队列头部任务优先级为3，队列中还有优先级为5的任务，优先级3任务被移到队列尾部；
然后打印优先级为5的任务，故其序号为1；
最后优先级为3的任务的序号为2。

四、解题思路

每次从队列头部取出第一个任务A，然后检查队列余下任务中有没有比A优先级更高的任务，如果有比A优先级高的任务，则将任务A放到队列尾部，否则就执行任务A的打印；
如果元素相同，保证原顺序，可以用优先队列实现，优先队列存储一个长度为2的数组，第一位是优先级，第二位是该任务出现的顺序；

如果弹出的优先级是最高的任务，即和优先队列弹出的优先级相同，添加打印顺序；
如果弹出的优先级不是最高的任务，即和优先队列弹出的优先级不相同；
- 将弹出首个优先级再次加入队列queue；
- 将弹出首个数组再次加入优先队列prior。

五、Java算法源码

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    // 每个任务的优先级
    int[] arr = Arrays.stream(sc.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();

    // 每个任务的优先级依次加入队列
    Queue<Integer> queue = new ArrayDeque<>();
    /**
     * 每个任务的优先级依次加入优先队列
     * int[2]:0是每个任务的优先级，1是每个任务的优先级对应的下角标
     * 如果优先级相同则比较下角标，按下角标升序排序
     * 如果优先级不同，则按优先级降序排序
     */
    PriorityQueue<int[]> prior = new PriorityQueue<>((a, b) -> (b[0] == a[0] ? a[1] - b[1] : b[0] - a[0]));
    int[] resultArr = new int[arr.length];
    for (int i = 0; i < arr.length; i++) {
        queue.offer(arr[i]);
        prior.offer(new int[]{arr[i], i});
    }

    // 打印顺序
    int n = 0;
    while(!queue.isEmpty()) {
        // 弹出首个优先级
        int poll = queue.poll();
        // 弹出首个数组
        int[] pollArr = prior.poll();
        // 如果弹出的优先级是最高的任务，即和优先队列弹出的优先级相同
        if (poll == pollArr[0]) {
            // 添加打印顺序
            resultArr[pollArr[1]] = n;
            n++;
        } else {// 如果弹出的优先级不是最高的任务，即和优先队列弹出的优先级不相同
            queue.offer(poll);// 将弹出首个优先级再次加入队列queue
            prior.offer(pollArr);// 将弹出首个数组再次加入优先队列prior
        }
    }

    // 每个任务的打印顺序
    StringJoiner joiner = new StringJoiner(",");
    for (int i = 0; i < resultArr.length; i++) {
        joiner.add(resultArr[i]+"");
    }
    System.out.println(joiner);
}