华为OD机试之打印机队列（Java源码）

打印机队列

题目描述

有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开始。

用例

输入	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
说明	无

源码和解析
解析：

1.可以使用有序列表对该题进行求解，但是这种每次添加任务队列都需要解决排序的问题，可以考虑在打印任务时再看是否有序，若无序，则可以排队，若有序，则直接输出首个任务，且直接移出这个任务。
2.另外一种方式就是使用大根堆去解决这个问题

示例代码方式一：

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;public class T35 {static class Task {int num;int priority;int taskId;public Task(int num, int priority, boolean isFinished,int taskId) {super();this.num = num;this.priority = priority;this.taskId = taskId;}@Overridepublic String toString() {return "Task [num=" + num + ", priority=" + priority+ ", taskId=" + taskId + "]\n";}}// 按输入的设备编号进行分堆 存放在不同的map中 键是打印机编号 值为该打印机的任务信息static Map<Integer, List<Task>> taskMap = new HashMap<Integer, List<Task>>();static List<Integer> pList = new ArrayList<>();// 记录设备的id集// 后面就不用keyset去遍历map了static boolean isOrdered = false;public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int num = scanner.nextInt();int id = 0;for (int i = 0; i < num; i++) {id++;String op = scanner.next();int p = scanner.nextInt();int priority = 0;if (op.equals("IN")) {priority = scanner.nextInt();}if (!taskMap.containsKey(p)) {List<Task> tasks = new ArrayList<T35.Task>();taskMap.put(p, tasks);pList.add(p);}Task task = new Task(p, priority, false, id);if (op.equals("IN")) {taskMap.get(p).add(task);isOrdered = false;} else {if (!isOrdered)sort();List<Task> tasksItem = taskMap.get(p);Task t = tasksItem.size() == 0 ? null : tasksItem.get(0);if (t != null) {tasksItem.remove(0);}System.out.println((t == null ? "NULL" : t.taskId));}}}// 排序public static void sort() {isOrdered = true;for (int p : pList) {taskMap.get(p).sort(new Comparator<Task>() {@Overridepublic int compare(Task o1, Task o2) {// 优先级降序 高的排前面 方便取值if (o1.priority > o2.priority) {return -1;} else if (o1.priority < o2.priority) {return 1;}// 优先级一样 任务顺序排序if (o1.taskId < o2.taskId) {return -1;} else if (o1.taskId > o2.taskId) {return 1;}return 0;}});}}
}

执行示意图如下：


大根堆解法
解析

例如输入
10
IN 1 2
IN 1 1
IN 1 4
IN 1 2
IN 1 4
IN 1 3
IN 1 5
OUT 1
OUT 2
OUT 2
形成的节点信息如下

那么在移出时就
OUT 1 针对 1 5 这个节点
OUT 1 查找到 1 5这个节点 无比他大 比他小的 那么只能是1 5 节点的父节点 1 4
OUT 1 查找到 1 4 节点是已完成的 那么可能就是1 3 节点 若1 3节点已完成 则可能是1 2 节点 若 1 2 节点已完成 则可能是其左节点1 1 若 1 1节点已完成 则看其左节点 若 1 1 节点未完成 则看其左节点
注意：这里并非是完全排序好的大根堆，而是依据节点的添加顺序形成的堆

源码示例 大根堆

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;public class T35 {static class Task {int devId; // 设备编号int priority;int taskId;boolean isFinished;Task leftTask; // 左节点Task rightTask; // 右节点Task parenTask;// 父节点@Overridepublic String toString() {return "Task [devId=" + devId + ", priority=" + priority+ ", taskId=" + taskId + "]\n";}}// 按输入的设备编号进行分堆 存放在不同的map中 键是打印机编号 值为该打印机的任务信息static Map<Integer, Task> taskMap = new HashMap<Integer, Task>();static Task objTask = null;public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int num = scanner.nextInt();int id = 0;for (int i = 0; i < num; i++) {id++;String op = scanner.next();int devId = scanner.nextInt();int priority = 0;if (op.equals("IN")) {priority = scanner.nextInt();}Task task = new Task();task.devId = devId;task.priority = priority;task.taskId = id;if (op.equals("IN")) {if (!taskMap.containsKey(devId)) {taskMap.put(devId, task);System.out.println("挂载跟节点：" + task.taskId);} else {// 挂载节点handle(devId, task);}} else {// 出节点objTask = null;find(taskMap.get(devId));if (objTask == null)System.out.println("NULL");}}}// 找到目标设备要出的那个public static void find(Task task) {if (task.isFinished == false) {// 自己未完成 那么可能到右侧if (task.rightTask != null && task.rightTask.isFinished == false) {find(task.rightTask);// 找右侧子节点 这种是不可能找左侧子节点的} else {// 到自己task.isFinished = true;objTask = task;System.out.println(task.taskId);// 输出任务id}} else {// 当前已完成 那么只有可能是其左侧节点if (task.leftTask != null)find(task.leftTask);}}public static void handle(int devId, Task task) {Task rootTask = taskMap.get(devId);mount(rootTask, task);}// 遍历节点 进行挂载public static void mount(Task task, Task objTask) {if (task.priority < objTask.priority) {// 挂载右侧if (task.rightTask != null) {mount(task.rightTask, objTask);} else {task.rightTask = objTask;System.out.println("节点" + objTask.taskId + "挂载在节点"+ task.taskId + "右侧");}} else {// 挂载左侧if (task.leftTask != null) {mount(task.leftTask, objTask);} else {task.leftTask = objTask;System.out.println("节点" + objTask.taskId + "挂载节点" + task.taskId+ "左侧");}}}
}

大根堆代码运行示意图：