网站建设挣钱么,wordpress wdone破解,网站app的作用,七星彩网投网站建设华为OD机试 2024E卷题库疯狂收录中#xff0c;刷题点这里 专栏导读
本专栏收录于《华为OD机试#xff08;JAVA#xff09;真题#xff08;E卷D卷A卷B卷C卷#xff09;》。
刷的越多#xff0c;抽中的概率越大#xff0c;私信哪吒#xff0c;备注华为OD#xff0c;加… 华为OD机试 2024E卷题库疯狂收录中刷题点这里 专栏导读
本专栏收录于《华为OD机试JAVA真题E卷D卷A卷B卷C卷》。
刷的越多抽中的概率越大私信哪吒备注华为OD加入华为OD刷题交流群每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景发现新题目随时更新全天CSDN在线答疑。
一、题目描述
有5台打印机打印文件每台打印机有自己的待打印队列。
因为打印的文件内容有轻重缓急之分所以队列中的文件有1~10 不同的 优先级其中数字越大优先级越高。
打印机会从自己的待打印队列中选取优先级最高的文件来打印。
如果存在两个优先级一样的文件则选择最早进入队列的那个文件。
现在请你来模拟这5台打印机的打印过程。
二、输入描述
每个输入包含1个测试用例
每个测试用例第一行给出发生事件的数量 N 0 N 1000。
接下来有 N 行分别表示发生的事件。共有如下两种事件
IN P NUM表示有一个拥有优先级 NUM 的文件放到了打印机 P 的待打印队列中。0 P 5, 0 NUM 10OUT P表示打印机 P 进行了一次文件打印同时该文件从待打印队列中取出。0 P 5。
三、输出描述
对于每个测试用例的每次 OUT P 事件请在一行中输出文件的编号。
如果此时没有文件可以打印请输出**“NULL”**。
文件的编号定义为为第 IN P NUM 事件发生第 x 次此处待打印文件的编号为 x。编号从1开始。
四、测试用例
测试用例1
1、输入
7 IN 1 1 IN 1 2 IN 1 3 IN 2 1 OUT 1 OUT 2 OUT 2
2、输出
3 4 NULL
3、说明
在打印机 1 的队列中插入了 3 个文件分别有不同的优先级其中编号 3 的文件优先级最高先被取出。
在打印机 2 的队列中插入了 1 个文件优先级为 1因此它被首先取出。
打印机 2 在第二次 OUT 操作时队列已经为空因此输出 “NULL”。
测试用例2
1、输入
6 IN 3 4 IN 3 5 IN 3 5 OUT 3 OUT 3 OUT 3
2、输出
2 3 1
3、说明
IN 3 4: 在打印机 3 的队列中插入优先级为 4 的文件文件编号为 1。IN 3 5: 在打印机 3 的队列中插入优先级为 5 的文件文件编号为 2。IN 3 5: 在打印机 3 的队列中插入优先级为 5 的文件文件编号为 3。OUT 3: 打印机 3 中有两个优先级 5 的文件文件编号为 2 的文件最早插入输出 2。OUT 3: 剩余优先级最高的文件是编号为 3 的文件优先级 5输出 3。OUT 3: 剩下的文件是编号为 1 的文件优先级 4输出 1。
五、解题思路
这个问题要求模拟打印机的文件调度过程关键在于正确处理每个打印机队列中的文件优先级和文件进入队列的顺序。在这个过程中我们需要解决以下几个问题
优先级处理每个文件有一个 1 到 10 的优先级数字越大优先级越高打印机应首先处理优先级最高的文件。
先进先出原则如果有多个文件的优先级相同应该按照它们进入队列的顺序来打印FIFO - First In First Out。
2、为什么采用优先队列
为了管理每个打印机的待打印队列我们为每台打印机使用一个 PriorityQueue优先队列数据结构。
PriorityQueue 是一种适合处理需要频繁获取最高优先级元素的问题的数据结构。它在插入和删除元素时能保持队列中元素的顺序以便随时可以取出优先级最高的元素。
在 Java 中PriorityQueue 是一个基于堆Heap的实现默认是小顶堆最小优先队列因此我们需要自定义比较器来实现大顶堆的行为最大优先队列。
3、具体步骤
创建 5 个 PriorityQueue 对象并存储在列表中每个 PriorityQueue 用于管理对应打印机的打印任务。对于 IN 事件将文件加入对应打印机的队列并根据文件的优先级进行排序。对于 OUT 事件从对应打印机的队列中取出优先级最高的文件如果队列为空则输出 “NULL”。根据处理结果输出文件编号或 “NULL”。
六、Java算法源码
public class OdTest01 {// 自定义类表示一个打印任务static class PrintJob {int priority; // 优先级int id; // 文件编号public PrintJob(int priority, int id) {this.priority priority;this.id id;}}public static void main(String[] args) {Scanner scanner new Scanner(System.in);// 读取事件数量int N scanner.nextInt();scanner.nextLine(); // 消耗换行符// 初始化打印机队列每个打印机用一个优先队列表示ListPriorityQueuePrintJob printers new ArrayList();for (int i 0; i 5; i) {printers.add(new PriorityQueue((a, b) - a.priority ! b.priority ? b.priority - a.priority : a.id - b.id));}int jobId 1; // 文件编号从1开始StringBuilder output new StringBuilder();// 处理每个事件for (int i 0; i N; i) {String[] parts scanner.nextLine().split( );String command parts[0];int printerIndex Integer.parseInt(parts[1]) - 1; // 打印机编号从1开始需要转为索引0-4if (IN.equals(command)) {int priority Integer.parseInt(parts[2]);// 创建新的打印任务并加入到对应的打印机队列中printers.get(printerIndex).offer(new PrintJob(priority, jobId));} else if (OUT.equals(command)) {// 从对应的打印机队列中取出优先级最高的文件PriorityQueuePrintJob queue printers.get(printerIndex);if (!queue.isEmpty()) {// 输出文件编号output.append(queue.poll().id).append(\n);} else {// 队列为空output.append(NULL\n);}}}// 输出结果System.out.print(output.toString());scanner.close();}
}七、效果展示
1、输入
4 IN 2 7 IN 2 7 OUT 2 OUT 2
2、输出
1 2
3、说明
两个 IN 操作分别在打印机 2 的队列中插入两个优先级为 7 的文件编号分别为 1 和 2。
第一个 OUT 操作取出优先级最高且最早进入队列的文件即编号 1。
第二个 OUT 操作取出剩下的唯一文件编号为 2。 下一篇华为OD机试 - 简易内存池 - 逻辑分析Java 2024 E卷 200分
本文收录于华为OD机试JAVA真题E卷D卷A卷B卷C卷
刷的越多抽中的概率越大私信哪吒备注华为OD加入华为OD刷题交流群每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景发现新题目随时更新全天CSDN在线答疑。
