晋城市网站建设管理人员,天津重型网站建设方案公司,wordpress 侧边收起,1sose wordpress打印机队列
题目描述 有5台打印机打印文件#xff0c;每台打印机有自己的待打印队列。 因为打印的文件内容有轻重缓急之分#xff0c;所以队列中的文件有1~10不同的代先级#xff0c;其中 数字越大优先级越高 打印机会从自己的待打印队列中选择优先级最高的文件来打印。 如…打印机队列
题目描述 有5台打印机打印文件每台打印机有自己的待打印队列。 因为打印的文件内容有轻重缓急之分所以队列中的文件有1~10不同的代先级其中 数字越大优先级越高 打印机会从自己的待打印队列中选择优先级最高的文件来打印。 如果存在两个优先级一样的文件则选择最早进入队列的那个文件。 现在请你来模拟这5台打印机的打印过程。 输入描述 每个输入包含1个测试用例 每个测试用例第一行给出发生事件的数量N0 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;}Overridepublic String toString() {return Task [num num , priority priority , taskId taskId ]\n;}}// 按输入的设备编号进行分堆 存放在不同的map中 键是打印机编号 值为该打印机的任务信息static MapInteger, ListTask taskMap new HashMapInteger, ListTask();static ListInteger 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)) {ListTask tasks new ArrayListT35.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();ListTask 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 ComparatorTask() {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 MapInteger, Task taskMap new HashMapInteger, 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 左侧);}}}
}
大根堆代码运行示意图
