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

打印机队列

题目描述

有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
说明	无

源码和解析
解析：

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;
		}

		@Override
		public 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>() {
				@Override
				public 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;// 父节点

		@Override
		public 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
						+ "左侧");
			}
		}
	}
}