【2024年华为OD机试】(A卷,100分)- 打印机队列（Java JS PythonC/C++）

一、问题描述

题目描述

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

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

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

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

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

输入描述

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

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

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

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

输出描述

对于每个测试用例，每次”OUT P”事件，请在一行中输出文件的编号。
如果此时没有文件可以打印，请输出”NULL“。
文件的编号定义为”IN P NUM”事件发生第 x 次，此处待打印文件的编号为x。编号从1开始。

用例

输入

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

输出

3
4
NULL

说明

无

输入

5
IN 1 1
IN 1 3
IN 1 1
IN 1 3
OUT 1

输出

2

说明

无

题目解析

本题可以基于优先队列实现打印机总是打印优先级最高的文件。

优先队列，如果想简单一点的话，则可以基于有序数组实现，但是有序数组是整体有序，每次有新任务入队，都需要O(n)时间复杂度维持。

优先队列最好是基于堆结构实现，所谓堆结构，即一颗完全二叉树。本题是优先级数值越大，优先级越高，因此我们可以使用大顶堆。

二、JavaScript算法源码

以下是基于有序数组实现优先队列的 JavaScript 代码的中文详细注释和逻辑讲解：

---

代码逻辑

// 引入 readline 模块，用于从控制台读取输入
const readline = require("readline");// 创建 readline 接口
const rl = readline.createInterface({input: process.stdin,  // 输入流为标准输入output: process.stdout, // 输出流为标准输出
});// 存储输入行的数组
const lines = [];
let n; // 存储任务的总数// 监听输入事件
rl.on("line", (line) => {lines.push(line); // 将每一行输入存入 lines 数组// 如果输入的第一行是任务总数 nif (lines.length === 1) {n = parseInt(lines[0]); // 解析 n 为整数}// 如果输入的行数等于 n + 1（任务总数 + 任务内容）if (n && lines.length === n + 1) {lines.shift(); // 移除第一行（任务总数）// 将剩余的行解析为任务数组const tasks = lines.map((line) => line.split(" "));// 调用算法函数处理任务getResult(tasks);// 清空 lines 数组，准备接收下一组输入lines.length = 0;}
});// 算法函数
function getResult(tasks) {// 使用对象存储每个打印机的任务队列const print = {};// 任务 ID，用于标识每个任务的唯一性let taskId = 1;// 遍历所有任务for (let i = 0; i < tasks.length; i++) {// 解析当前任务的类型、打印机 ID 和优先级const [type, printId, priority] = tasks[i];// 如果是 "IN" 操作（添加任务）if (type === "IN") {// 创建一个任务数组，包含任务 ID、优先级和任务顺序const arr = [taskId, priority, i]; // i 是先来后到的顺序// 如果当前打印机 ID 不存在，初始化一个空数组if (!print[printId]) {print[printId] = []; // 基于数组实现优先队列}// 将任务添加到对应打印机的任务队列中print[printId].push(arr);// 对任务队列进行排序，维持高优先级在头部// 如果优先级相同，则按先来后到的顺序排序print[printId].sort((a, b) => (a[1] != b[1] ? b[1] - a[1] : a[2] - b[2]));// 任务 ID 自增taskId++;}// 如果是 "OUT" 操作（取出任务）else {// 如果当前打印机 ID 不存在或任务队列为空，输出 "NULL"if (!print[printId] || print[printId].length == 0) {console.log("NULL");}// 否则，取出队列中的第一个任务并输出任务 IDelse {const arr = print[printId].shift(); // 移除队列中的第一个任务console.log(arr ? arr[0] : "NULL"); // 输出任务 ID}}}
}

---

代码讲解

1. 输入处理：

   • 使用 readline 模块从控制台读取输入。
   • 第一行输入为任务总数 n。
   • 后续 n 行输入为任务内容，每行包含任务类型（IN 或 OUT）、打印机 ID 和优先级（仅 IN 操作需要）。

2. 任务队列存储：

   • 使用对象 print 存储每个打印机的任务队列。
   • 每个打印机的任务队列是一个数组，数组中的每个元素是一个任务，包含任务 ID、优先级和任务顺序。

3. 任务添加（IN 操作）：

   • 解析任务内容，生成任务数组 [taskId, priority, i]，其中：
     • taskId：任务的唯一标识。
     • priority：任务的优先级。
     • i：任务的顺序（先来后到）。
   • 将任务添加到对应打印机的任务队列中。
   • 对任务队列进行排序，优先级高的任务排在前面。如果优先级相同，则按任务顺序排序。

4. 任务取出（OUT 操作）：

   • 检查对应打印机的任务队列是否为空。
   • 如果队列为空，输出 "NULL"。
   • 如果队列不为空，取出队列中的第一个任务并输出任务 ID。

5. 任务 ID 管理：

   • 使用 taskId 变量为每个任务分配唯一的 ID，确保任务的唯一性。

6. 排序逻辑：

   • 使用 sort 方法对任务队列进行排序：
     • 优先级高的任务排在前面（b[1] - a[1]）。
     • 如果优先级相同，则按任务顺序排序（a[2] - b[2]）。

---

示例解析

输入

5
IN 1 10
IN 1 20
OUT 1
IN 1 30
OUT 1

运行结果

2
3

• 解析：
  • 第 1 个任务：IN 1 10，任务 ID 为 1，优先级为 10。
  • 第 2 个任务：IN 1 20，任务 ID 为 2，优先级为 20。
  • 第 3 个任务：OUT 1，取出打印机 1 的任务队列中的第一个任务（优先级最高），输出任务 ID 2。
  • 第 4 个任务：IN 1 30，任务 ID 为 3，优先级为 30。
  • 第 5 个任务：OUT 1，取出打印机 1 的任务队列中的第一个任务（优先级最高），输出任务 ID 3。

---

总结

• 该代码基于有序数组实现了优先队列，支持任务的添加和取出操作。
• 通过排序逻辑，确保高优先级任务优先处理，同时支持任务顺序的优先级。
• 适用于需要动态管理任务队列的场景，如打印机任务调度等。

如果有其他问题，欢迎随时提问！

三、Java算法源码

以下是基于 Java 的 PriorityQueue 实现优先队列的代码的中文详细注释和逻辑讲解：

---

代码逻辑

import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.Scanner;public class Main {public static void main(String[] args) {// 创建 Scanner 对象，用于从控制台读取输入Scanner sc = new Scanner(System.in);// 读取任务总数 nint n = Integer.parseInt(sc.nextLine());// 定义二维数组 tasks，用于存储所有任务String[][] tasks = new String[n][];// 读取 n 行任务内容，并存入 tasks 数组for (int i = 0; i < n; i++) {String[] s = sc.nextLine().split(" "); // 将每行输入按空格分割tasks[i] = s; // 存入 tasks 数组}// 调用算法函数处理任务getResult(tasks);}public static void getResult(String[][] tasks) {// 使用 HashMap 存储每台打印机的等待队列// key: 打印机 ID，value: 优先队列（存储打印任务）HashMap<String, PriorityQueue<int[]>> print = new HashMap<>();// 文件编号，从 1 开始int x = 1;// 遍历所有任务for (int i = 0; i < tasks.length; i++) {// 获取当前任务String[] task = tasks[i];// 解析任务类型（IN 或 OUT）和打印机 IDString type = task[0];String printId = task[1];// 如果是 "IN" 操作（添加任务）if ("IN".equals(type)) {// 解析任务的优先级String priority = task[2];// 创建打印任务数组，包含文件编号、优先级和任务顺序int[] arr = {x, Integer.parseInt(priority), i}; // i 代表先来后到的顺序// 如果当前打印机 ID 不存在，初始化一个优先队列print.putIfAbsent(printId,new PriorityQueue<>((a, b) ->a[1] != b[1] ? b[1] - a[1] : a[2] - b[2])); // 优先按优先级排序，如果优先级相同，按任务顺序排序// 将打印任务加入对应打印机的优先队列print.get(printId).offer(arr);// 文件编号自增x++;}// 如果是 "OUT" 操作（取出任务）else {// 检查当前打印机的等待队列是否为空if (!print.containsKey(printId) || print.get(printId).isEmpty()) {// 如果队列为空，输出 "NULL"System.out.println("NULL");} else {// 取出队列中优先级最高的任务int[] arr = print.get(printId).poll();// 输出任务的文件编号if (arr != null) System.out.println(arr[0]); // arr[0] 是文件编号 xelse System.out.println("NULL");}}}}
}

---

代码讲解

1. 输入处理：

   • 使用 Scanner 从控制台读取输入。
   • 第一行输入为任务总数 n。
   • 后续 n 行输入为任务内容，每行包含任务类型（IN 或 OUT）、打印机 ID 和优先级（仅 IN 操作需要）。

2. 任务队列存储：

   • 使用 HashMap 存储每台打印机的任务队列。
   • HashMap 的 key 是打印机 ID，value 是一个优先队列（PriorityQueue），用于存储打印任务。

3. 任务添加（IN 操作）：

   • 解析任务内容，生成任务数组 [x, priority, i]，其中：
     • x：文件编号，唯一标识任务。
     • priority：任务的优先级。
     • i：任务的顺序（先来后到）。
   • 如果当前打印机 ID 不存在，初始化一个优先队列，并设置排序规则：
     • 优先级高的任务排在前面（b[1] - a[1]）。
     • 如果优先级相同，则按任务顺序排序（a[2] - b[2]）。
   • 将任务添加到对应打印机的优先队列中。

4. 任务取出（OUT 操作）：

   • 检查对应打印机的任务队列是否为空。
   • 如果队列为空，输出 "NULL"。
   • 如果队列不为空，取出队列中优先级最高的任务，并输出任务的文件编号。

5. 文件编号管理：

   • 使用变量 x 为每个任务分配唯一的文件编号，确保任务的唯一性。

6. 优先队列排序规则：

   • 优先队列的排序规则通过 Comparator 实现：
     • 优先级高的任务排在前面。
     • 如果优先级相同，则按任务顺序排序。

---

示例解析

输入

5
IN 1 10
IN 1 20
OUT 1
IN 1 30
OUT 1

运行结果

2
3

• 解析：
  • 第 1 个任务：IN 1 10，文件编号为 1，优先级为 10。
  • 第 2 个任务：IN 1 20，文件编号为 2，优先级为 20。
  • 第 3 个任务：OUT 1，取出打印机 1 的任务队列中的第一个任务（优先级最高），输出文件编号 2。
  • 第 4 个任务：IN 1 30，文件编号为 3，优先级为 30。
  • 第 5 个任务：OUT 1，取出打印机 1 的任务队列中的第一个任务（优先级最高），输出文件编号 3。

---

总结

• 该代码基于 Java 的 PriorityQueue 实现了优先队列，支持任务的添加和取出操作。
• 通过自定义排序规则，确保高优先级任务优先处理，同时支持任务顺序的优先级。
• 适用于需要动态管理任务队列的场景，如打印机任务调度等。

如果有其他问题，欢迎随时提问！

四、Python算法源码

以下是基于 Python 的 queue.PriorityQueue 实现优先队列的代码的中文详细注释和逻辑讲解：

---

代码逻辑

import queue# 输入获取
n = int(input())  # 读取任务总数 ntasks = []  # 定义列表 tasks，用于存储所有任务
for i in range(n):tasks.append(input().split())  # 读取每行任务内容，并存入 tasks 列表# 定义 Task 类，用于表示打印任务
class Task:def __init__(self, taskId, priority, index):"""构造函数，初始化任务对象:param taskId: 任务 ID:param priority: 任务优先级:param index: 任务到达顺序"""self.taskId = taskIdself.priority = priorityself.index = indexdef __lt__(self, other):"""重载小于运算符，定义任务的排序规则:param other: 另一个任务对象:return: 当前任务是否优先于另一个任务"""if self.priority != other.priority:return self.priority > other.priority  # 优先级高的任务优先else:return self.index < other.index  # 如果优先级相同，按任务到达顺序排序# 算法入口
def getResult(tasks):# 使用字典 printer 存储每台打印机的任务队列# key: 打印机 ID，value: 优先队列（存储 Task 对象）printer = {}# 任务 ID，从 1 开始taskId = 1# 遍历所有任务for i in range(len(tasks)):task = tasks[i]  # 获取当前任务# 解析任务类型（IN 或 OUT）和打印机 IDtype = task[0]printerId = task[1]# 如果是 "IN" 操作（添加任务）if type == "IN":# 解析任务的优先级priority = task[2]# 如果当前打印机 ID 不存在，初始化一个优先队列if printer.get(printerId) is None:printer[printerId] = queue.PriorityQueue()# 创建 Task 对象，表示当前任务t = Task(taskId, int(priority), i)# 将任务加入对应打印机的优先队列printer[printerId].put(t)# 任务 ID 自增taskId += 1# 如果是 "OUT" 操作（取出任务）else:# 检查当前打印机的任务队列是否为空if printer.get(printerId) is None or printer[printerId].qsize() == 0:# 如果队列为空，输出 "NULL"print("NULL")else:# 取出队列中优先级最高的任务t = printer[printerId].get()# 输出任务的任务 IDprint(t.taskId)# 调用算法函数处理任务
getResult(tasks)

---

代码讲解

1. 输入处理：

   • 使用 input() 函数从控制台读取输入。
   • 第一行输入为任务总数 n。
   • 后续 n 行输入为任务内容，每行包含任务类型（IN 或 OUT）、打印机 ID 和优先级（仅 IN 操作需要）。

2. 任务队列存储：

   • 使用字典 printer 存储每台打印机的任务队列。
   • 字典的 key 是打印机 ID，value 是一个优先队列（queue.PriorityQueue），用于存储 Task 对象。

3. 任务添加（IN 操作）：

   • 解析任务内容，创建 Task 对象，包含任务 ID、优先级和任务顺序。
   • 如果当前打印机 ID 不存在，初始化一个优先队列。
   • 将任务添加到对应打印机的优先队列中。

4. 任务取出（OUT 操作）：

   • 检查对应打印机的任务队列是否为空。
   • 如果队列为空，输出 "NULL"。
   • 如果队列不为空，取出队列中优先级最高的任务，并输出任务的任务 ID。

5. 任务排序规则：

   • 在 Task 类中重载 __lt__ 方法，定义任务的排序规则：
     • 优先级高的任务优先（self.priority > other.priority）。
     • 如果优先级相同，则按任务到达顺序排序（self.index < other.index）。

6. 任务 ID 管理：

   • 使用变量 taskId 为每个任务分配唯一的任务 ID，确保任务的唯一性。

---

示例解析

输入

5
IN 1 10
IN 1 20
OUT 1
IN 1 30
OUT 1

运行结果

2
3

• 解析：
  • 第 1 个任务：IN 1 10，任务 ID 为 1，优先级为 10。
  • 第 2 个任务：IN 1 20，任务 ID 为 2，优先级为 20。
  • 第 3 个任务：OUT 1，取出打印机 1 的任务队列中的第一个任务（优先级最高），输出任务 ID 2。
  • 第 4 个任务：IN 1 30，任务 ID 为 3，优先级为 30。
  • 第 5 个任务：OUT 1，取出打印机 1 的任务队列中的第一个任务（优先级最高），输出任务 ID 3。

---

总结

• 该代码基于 Python 的 queue.PriorityQueue 实现了优先队列，支持任务的添加和取出操作。
• 通过重载 __lt__ 方法，定义任务的排序规则，确保高优先级任务优先处理，同时支持任务顺序的优先级。
• 适用于需要动态管理任务队列的场景，如打印机任务调度等。

如果有其他问题，欢迎随时提问！

五、C/C++算法源码：

以下是基于 C++ 的 priority_queue 实现优先队列的代码的中文详细注释和逻辑讲解：

---

代码逻辑

#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <sstream>
using namespace std;// 任务类
class Task {
public:int taskId;    // 任务IDint priority;  // 任务优先级int index;     // 任务到达顺序// 构造函数，初始化任务对象Task(int taskId, int priority, int index) : taskId(taskId), priority(priority), index(index) {}// 重载小于运算符，用于优先队列的比较bool operator<(const Task& other) const {if (priority != other.priority) {return priority < other.priority; // 优先级高的排在前面} else {return index > other.index; // 优先级相同，先到的排在前面}}
};// 输入获取
int n;  // 任务总数
vector<vector<string>> tasks;  // 存储所有任务的二维数组void readInput() {cin >> n;  // 读取任务总数tasks.resize(n);  // 调整 tasks 的大小为 nfor (int i = 0; i < n; ++i) {string line;cin >> line;  // 读取每行任务内容stringstream ss(line);  // 使用字符串流分割任务内容string token;while (ss >> token) {tasks[i].push_back(token);  // 将分割后的任务内容存入 tasks}}
}// 算法入口
void getResult() {// 定义 6 个优先队列，分别对应 6 个打印机（编号 1-5）vector<priority_queue<Task>> printer(6);// 任务 ID，从 1 开始int taskId = 1;// 遍历所有任务for (int i = 0; i < n; ++i) {const vector<string>& task = tasks[i];  // 获取当前任务// 解析任务类型（IN 或 OUT）和打印机 IDstring type = task[0];int printerId = stoi(task[1]);// 如果是 "IN" 操作（添加任务）if (type == "IN") {// 解析任务的优先级int priority = stoi(task[2]);// 将任务加入对应打印机的优先队列printer[printerId].emplace(taskId, priority, i);// 任务 ID 自增taskId++;}// 如果是 "OUT" 操作（取出任务）else {// 检查当前打印机的任务队列是否为空if (printer[printerId].empty()) {// 如果队列为空，输出 "NULL"cout << "NULL" << endl;} else {// 取出队列中优先级最高的任务Task t = printer[printerId].top();printer[printerId].pop();// 输出任务的任务 IDcout << t.taskId << endl;}}}
}int main() {readInput();  // 读取输入getResult();  // 处理任务return 0;
}

---

代码讲解

1. 输入处理：

   • 使用 cin 从控制台读取输入。
   • 第一行输入为任务总数 n。
   • 后续 n 行输入为任务内容，每行包含任务类型（IN 或 OUT）、打印机 ID 和优先级（仅 IN 操作需要）。
   • 使用 stringstream 分割每行任务内容，并存入二维数组 tasks。

2. 任务队列存储：

   • 使用 vector<priority_queue<Task>> 存储 6 个打印机的任务队列（编号 1-5）。
   • 每个优先队列（priority_queue）存储 Task 对象。

3. 任务添加（IN 操作）：

   • 解析任务内容，创建 Task 对象，包含任务 ID、优先级和任务顺序。
   • 将任务加入对应打印机的优先队列中。

4. 任务取出（OUT 操作）：

   • 检查对应打印机的任务队列是否为空。
   • 如果队列为空，输出 "NULL"。
   • 如果队列不为空，取出队列中优先级最高的任务，并输出任务的任务 ID。

5. 任务排序规则：

   • 在 Task 类中重载 < 运算符，定义任务的排序规则：
     • 优先级高的任务优先（priority < other.priority）。
     • 如果优先级相同，则按任务到达顺序排序（index > other.index）。

6. 任务 ID 管理：

   • 使用变量 taskId 为每个任务分配唯一的任务 ID，确保任务的唯一性。

---

示例解析

输入

5
IN 1 10
IN 1 20
OUT 1
IN 1 30
OUT 1

运行结果

2
3

• 解析：
  • 第 1 个任务：IN 1 10，任务 ID 为 1，优先级为 10。
  • 第 2 个任务：IN 1 20，任务 ID 为 2，优先级为 20。
  • 第 3 个任务：OUT 1，取出打印机 1 的任务队列中的第一个任务（优先级最高），输出任务 ID 2。
  • 第 4 个任务：IN 1 30，任务 ID 为 3，优先级为 30。
  • 第 5 个任务：OUT 1，取出打印机 1 的任务队列中的第一个任务（优先级最高），输出任务 ID 3。

---

总结

• 该代码基于 C++ 的 priority_queue 实现了优先队列，支持任务的添加和取出操作。
• 通过重载 < 运算符，定义任务的排序规则，确保高优先级任务优先处理，同时支持任务顺序的优先级。
• 适用于需要动态管理任务队列的场景，如打印机任务调度等。

如果有其他问题，欢迎随时提问！