华为OD机试 - 打印机队列 - 优先队列（Java 2024 E卷 200分）

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

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

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

有5台打印机打印文件，每台打印机有自己的待打印队列。

因为打印的文件内容有轻重缓急之分，所以队列中的文件有1~10 不同的 优先级，其中数字越大优先级越高。

打印机会从自己的待打印队列中选取优先级最高的文件来打印。

如果存在两个优先级一样的文件，则选择最早进入队列的那个文件。

现在请你来模拟这5台打印机的打印过程。

二、输入描述

每个输入包含1个测试用例，

每个测试用例第一行给出发生事件的数量 N （0 < N < 1000）。

接下来有 N 行，分别表示发生的事件。共有如下两种事件：

1. IN P NUM，表示有一个拥有优先级 NUM 的文件放到了打印机 P 的待打印队列中。（0 < P <= 5, 0 < NUM <= 10）；
2. OUT P，表示打印机 P 进行了一次文件打印，同时该文件从待打印队列中取出。（0 < P <= 5）。

三、输出描述

对于每个测试用例的，每次 OUT P 事件，请在一行中输出文件的编号。

如果此时没有文件可以打印，请输出**“NULL”**。

文件的编号定义为为第 IN P NUM 事件发生第 x 次，此处待打印文件的编号为 x。编号从1开始。

四、测试用例

测试用例1：

1、输入

7
IN 1 1
IN 1 2
IN 1 3
IN 2 1
OUT 1
OUT 2
OUT 2

2、输出

3
4
NULL

3、说明

在打印机 1 的队列中插入了 3 个文件，分别有不同的优先级，其中编号 3 的文件优先级最高，先被取出。

在打印机 2 的队列中插入了 1 个文件，优先级为 1，因此它被首先取出。

打印机 2 在第二次 OUT 操作时队列已经为空，因此输出 “NULL”。

测试用例2：

1、输入

6
IN 3 4
IN 3 5
IN 3 5
OUT 3
OUT 3
OUT 3

2、输出

2
3
1

3、说明

• IN 3 4: 在打印机 3 的队列中插入优先级为 4 的文件，文件编号为 1。
• IN 3 5: 在打印机 3 的队列中插入优先级为 5 的文件，文件编号为 2。
• IN 3 5: 在打印机 3 的队列中插入优先级为 5 的文件，文件编号为 3。
• OUT 3: 打印机 3 中有两个优先级 5 的文件，文件编号为 2 的文件最早插入，输出 2。
• OUT 3: 剩余优先级最高的文件是编号为 3 的文件（优先级 5），输出 3。
• OUT 3: 剩下的文件是编号为 1 的文件（优先级 4），输出 1。

五、解题思路

这个问题要求模拟打印机的文件调度过程，关键在于正确处理每个打印机队列中的文件优先级和文件进入队列的顺序。在这个过程中，我们需要解决以下几个问题：

优先级处理：每个文件有一个 1 到 10 的优先级，数字越大优先级越高，打印机应首先处理优先级最高的文件。

先进先出原则：如果有多个文件的优先级相同，应该按照它们进入队列的顺序来打印（FIFO - First In First Out）。

2、为什么采用优先队列？

为了管理每个打印机的待打印队列，我们为每台打印机使用一个 PriorityQueue（优先队列）数据结构。

PriorityQueue 是一种适合处理需要频繁获取最高优先级元素的问题的数据结构。它在插入和删除元素时能保持队列中元素的顺序，以便随时可以取出优先级最高的元素。

在 Java 中，PriorityQueue 是一个基于堆（Heap）的实现，默认是小顶堆（最小优先队列），因此我们需要自定义比较器来实现大顶堆的行为（最大优先队列）。

3、具体步骤：

1. 创建 5 个 PriorityQueue 对象并存储在列表中，每个 PriorityQueue 用于管理对应打印机的打印任务。
2. 对于 IN 事件，将文件加入对应打印机的队列，并根据文件的优先级进行排序。
3. 对于 OUT 事件，从对应打印机的队列中取出优先级最高的文件，如果队列为空则输出 “NULL”。
4. 根据处理结果输出文件编号或 “NULL”。

六、Java算法源码

public class OdTest01 {// 自定义类表示一个打印任务static class PrintJob {int priority; // 优先级int id; // 文件编号public PrintJob(int priority, int id) {this.priority = priority;this.id = id;}}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 读取事件数量int N = scanner.nextInt();scanner.nextLine(); // 消耗换行符// 初始化打印机队列，每个打印机用一个优先队列表示List<PriorityQueue<PrintJob>> printers = new ArrayList<>();for (int i = 0; i < 5; i++) {printers.add(new PriorityQueue<>((a, b) -> a.priority != b.priority ? b.priority - a.priority : a.id - b.id));}int jobId = 1; // 文件编号，从1开始StringBuilder output = new StringBuilder();// 处理每个事件for (int i = 0; i < N; i++) {String[] parts = scanner.nextLine().split(" ");String command = parts[0];int printerIndex = Integer.parseInt(parts[1]) - 1; // 打印机编号从1开始，需要转为索引0-4if ("IN".equals(command)) {int priority = Integer.parseInt(parts[2]);// 创建新的打印任务并加入到对应的打印机队列中printers.get(printerIndex).offer(new PrintJob(priority, jobId++));} else if ("OUT".equals(command)) {// 从对应的打印机队列中取出优先级最高的文件PriorityQueue<PrintJob> queue = printers.get(printerIndex);if (!queue.isEmpty()) {// 输出文件编号output.append(queue.poll().id).append("\n");} else {// 队列为空output.append("NULL\n");}}}// 输出结果System.out.print(output.toString());scanner.close();}
}

七、效果展示

1、输入

4
IN 2 7
IN 2 7
OUT 2
OUT 2

2、输出

1
2

3、说明

两个 IN 操作分别在打印机 2 的队列中插入两个优先级为 7 的文件，编号分别为 1 和 2。

第一个 OUT 操作取出优先级最高且最早进入队列的文件，即编号 1。

第二个 OUT 操作取出剩下的唯一文件，编号为 2。

🏆下一篇：华为OD机试 - 简易内存池 - 逻辑分析（Java 2024 E卷 200分）

🏆本文收录于，华为OD机试（JAVA）真题（E卷+D卷+A卷+B卷+C卷）

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。