(100分)- 打印机队列（Java JS Python）-平芜编程栈

(100分)- 打印机队列（Java & JS & Python）

题目描述

有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 Node ACM模式 控制台输入获取 */ const readline = require("readline"); const rl = readline.createInterface({ input: process.stdin, output: process.stdout, }); const lines = []; let n; rl.on("line", (line) => { lines.push(line); if (lines.length === 1) { n = parseInt(lines[0]); } if (n && lines.length === n + 1) { lines.shift(); const tasks = lines.map((line) => line.split(" ")); getResult(tasks); lines.length = 0; } }); function getResult(tasks) { const print = {}; let taskId = 1; for (let i = 0; i < tasks.length; i++) { const [type, printId, priority] = tasks[i]; if (type === "IN") { const arr = [taskId, priority, i]; // i 是先来后到的顺序 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])); // 维持高优先级在头部，如果优先级相同，则按先来后到 taskId++; } else { if (!print[printId] || print[printId].length == 0) { console.log("NULL"); } else { const arr = print[printId].shift(); console.log(arr ? arr[0] : "NULL"); } } } }

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 sc = new Scanner(System.in); int n = Integer.parseInt(sc.nextLine()); String[][] tasks = new String[n][]; for (int i = 0; i < n; i++) { String[] s = sc.nextLine().split(" "); tasks[i] = s; } getResult(tasks); } public static void getResult(String[][] tasks) { // print中存放每台打印机的等待队列 HashMap<String, PriorityQueue<int[]>> print = new HashMap<>(); // 文件的编号定义为”IN P NUM”事件发生第 x 次，此处待打印文件的编号为x。编号从1开始。 int x = 1; for (int i = 0; i < tasks.length; i++) { String[] task = tasks[i]; // IN,OUT都有type和printId String type = task[0]; String printId = task[1]; if ("IN".equals(type)) { // IN还有priority String priority = task[2]; // arr是打印任务 int[] arr = {x, Integer.parseInt(priority), i}; // i代表先来后到的顺序 // 为打印机printId设置打印优先级，打印任务的priority越大，优先级越高 print.putIfAbsent( printId, new PriorityQueue<>( (a, b) -> a[1] != b[1] ? b[1] - a[1] : a[2] - b[2])); // 优先按priority，如果priority相同，按先来后到i // 将打印任务加入对应打印机 print.get(printId).offer(arr); x++; } else { // 打印机等待队列中取出优先级最高的打印任务arr 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]是x else System.out.println("NULL"); } } } } }

Python算法源码

import queue # 输入获取 n = int(input()) tasks = [] for i in range(n): tasks.append(input().split()) class Task: def __init__(self, taskId, priority, index): """ :param taskId: 任务ID :param priority: 任务优先级 :param index: 任务到达顺序 """ self.taskId = taskId self.priority = priority self.index = index def __lt__(self, other): if self.priority != other.priority: return self.priority > other.priority else: return self.index < other.index # 算法入口 def getResult(tasks): printer = {} taskId = 1 for i in range(len(tasks)): task = tasks[i] type = task[0] printerId = task[1] if type == "IN": priority = task[2] if printer.get(printerId) is None: printer[printerId] = queue.PriorityQueue() printer[printerId].put(Task(taskId, int(priority), i)) taskId += 1 else: if printer.get(printerId) is None or printer[printerId].qsize() == 0: print("NULL") else: t = printer[printerId].get() print(t.taskId) getResult(tasks)