当前位置： 首页 > article >正文

华为OD机试 - 打印机队列 - 优先队列（Python/JS/C/C++ 2024 E卷 200分）

article 2024/9/20 1:06:13

在这里插入图片描述

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

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

四、测试用例

测试用例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。

测试用例3：

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。

五、解题思路

这个问题要求模拟打印机的文件调度过程，关键在于正确处理每个打印机队列中的文件优先级和文件进入队列的顺序。在这个过程中，我们需要解决以下几个问题：

优先级处理：每个文件有一个 1 到 10 的优先级，数字越大优先级越高，打印机应首先处理优先级最高的文件。

先进先出原则：如果有多个文件的优先级相同，应该按照它们进入队列的顺序来打印（FIFO - First In First Out）。

2、为什么采用优先队列？

为了管理每个打印机的待打印队列，我们为每台打印机使用一个 PriorityQueue（优先队列）数据结构。

PriorityQueue 是一种适合处理需要频繁获取最高优先级元素的问题的数据结构。它在插入和删除元素时能保持队列中元素的顺序，以便随时可以取出优先级最高的元素。

在 Java 中，PriorityQueue 是一个基于堆（Heap）的实现，默认是小顶堆（最小优先队列），因此我们需要自定义比较器来实现大顶堆的行为（最大优先队列）。

3、具体步骤：

  1. 创建 5 个 PriorityQueue 对象并存储在列表中，每个 PriorityQueue 用于管理对应打印机的打印任务。
  2. 对于 IN 事件，将文件加入对应打印机的队列，并根据文件的优先级进行排序。
  3. 对于 OUT 事件，从对应打印机的队列中取出优先级最高的文件，如果队列为空则输出 “NULL”。
  4. 根据处理结果输出文件编号或 “NULL”。

六、Python算法源码

import heapq  # 导入heapq模块，用于创建优先队列

# 自定义类表示一个打印任务
class PrintJob:
    def __init__(self, priority, id):
        # 初始化优先级和文件编号
        self.priority = priority
        self.id = id

    # 定义比较规则，用于在优先队列中排序
    def __lt__(self, other):
        if self.priority != other.priority:
            return self.priority > other.priority  # 优先级高的任务优先处理
        return self.id < other.id  # 优先级相同时，编号小的任务优先处理

def main():
    N = int(input().strip())  # 读取事件数量，并去除多余的空格
    
    # 初始化5个打印机的优先队列，每个队列用列表表示
    printers = [[] for _ in range(5)]
    jobId = 1  # 文件编号从1开始
    output = []  # 用于存储输出的结果

    # 处理每个事件
    for _ in range(N):
        parts = input().split()  # 按空格分割输入
        command = parts[0]  # 获取命令类型
        printerIndex = int(parts[1]) - 1  # 获取打印机编号，并转换为0-4的索引

        if command == "IN":
            priority = int(parts[2])  # 获取任务优先级
            # 将新的打印任务加入到对应的打印机队列中
            heapq.heappush(printers[printerIndex], PrintJob(priority, jobId))
            jobId += 1  # 文件编号递增
        elif command == "OUT":
            # 检查对应打印机队列是否为空
            if printers[printerIndex]:
                # 输出优先级最高的文件编号
                output.append(str(heapq.heappop(printers[printerIndex]).id))
            else:
                output.append("NULL")  # 如果队列为空，输出"NULL"

    # 打印最终的输出结果，每个结果占一行
    print("\n".join(output))

if __name__ == "__main__":
    main()

七、JavaScript算法源码

// 定义一个类表示打印任务
class PrintJob {
    constructor(priority, id) {
        this.priority = priority; // 初始化优先级
        this.id = id;             // 初始化文件编号
    }
}

// 定义一个优先队列类，用于管理打印任务
class PriorityQueue {
    constructor() {
        this.queue = [];  // 初始化为空数组
    }

    // 将任务加入队列，并根据优先级排序
    offer(job) {
        this.queue.push(job);
        this.queue.sort((a, b) => {
            if (a.priority !== b.priority) return b.priority - a.priority;  // 优先级高的排前面
            return a.id - b.id;  // 如果优先级相同，文件编号小的排前面
        });
    }

    // 取出优先级最高的任务
    poll() {
        return this.queue.shift();  // 从队列头部取出任务
    }

    // 判断队列是否为空
    isEmpty() {
        return this.queue.length === 0;  // 如果队列长度为0，则为空
    }
}

function main() {
    const input = require('fs').readFileSync('/dev/stdin', 'utf8').trim().split('\n'); // 读取输入
    const N = parseInt(input[0].trim());  // 获取事件数量
    const printers = Array.from({ length: 5 }, () => new PriorityQueue());  // 初始化5个打印机
    let jobId = 1;  // 文件编号从1开始
    let output = [];  // 存储输出结果

    for (let i = 1; i <= N; i++) {
        const parts = input[i].split(' ');  // 按空格分割每行输入
        const command = parts[0];  // 获取命令类型
        const printerIndex = parseInt(parts[1]) - 1;  // 将打印机编号转为索引

        if (command === "IN") {
            const priority = parseInt(parts[2]);  // 获取任务优先级
            printers[printerIndex].offer(new PrintJob(priority, jobId++));  // 创建并加入新任务
        } else if (command === "OUT") {
            if (!printers[printerIndex].isEmpty()) {
                output.push(printers[printerIndex].poll().id);  // 输出文件编号
            } else {
                output.push("NULL");  // 队列为空时输出NULL
            }
        }
    }

    console.log(output.join('\n'));  // 输出结果
}

main();

八、C算法源码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 定义结构体表示打印任务
typedef struct {
    int priority;  // 优先级
    int id;        // 文件编号
} PrintJob;

// 比较函数，用于任务排序
int compare(const void *a, const void *b) {
    PrintJob *jobA = (PrintJob *)a;
    PrintJob *jobB = (PrintJob *)b;
    if (jobA->priority != jobB->priority)
        return jobB->priority - jobA->priority;  // 优先级高的排在前
    return jobA->id - jobB->id;  // 编号小的排在前
}

// 定义优先队列结构体
typedef struct {
    PrintJob jobs[1000];  // 存储任务的数组
    int size;             // 当前队列中的任务数
} PriorityQueue;

// 将新任务加入优先队列，并排序
void push(PriorityQueue *pq, PrintJob job) {
    pq->jobs[pq->size++] = job;
    qsort(pq->jobs, pq->size, sizeof(PrintJob), compare);  // 排序
}

// 取出优先级最高的任务
PrintJob pop(PriorityQueue *pq) {
    return pq->jobs[--pq->size];  // 返回最后一个任务
}

// 判断队列是否为空
int isEmpty(PriorityQueue *pq) {
    return pq->size == 0;  // 如果任务数为0，则队列为空
}

int main() {
    int N;
    scanf("%d", &N);  // 读取事件数量
    
    PriorityQueue printers[5] = {0};  // 初始化5个打印机队列
    int jobId = 1;  // 文件编号从1开始

    for (int i = 0; i < N; i++) {
        char command[4];
        int printerIndex;
        scanf("%s %d", command, &printerIndex);  // 读取命令和打印机编号
        printerIndex--;  // 将打印机编号转换为索引

        if (strcmp(command, "IN") == 0) {
            int priority;
            scanf("%d", &priority);  // 获取任务优先级
            PrintJob newJob = {priority, jobId++};  // 创建新任务
            push(&printers[printerIndex], newJob);  // 将任务加入队列
        } else if (strcmp(command, "OUT") == 0) {
            if (!isEmpty(&printers[printerIndex])) {
                PrintJob job = pop(&printers[printerIndex]);  // 取出优先级最高的任务
                printf("%d\n", job.id);  // 输出任务编号
            } else {
                printf("NULL\n");  // 队列为空时输出NULL
            }
        }
    }

    return 0;
}

九、C++算法源码

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

// 定义结构体表示打印任务
struct PrintJob {
    int priority;  // 优先级
    int id;        // 文件编号

    // 自定义比较函数，用于优先队列排序
    bool operator<(const PrintJob &other) const {
        if (priority != other.priority) {
            return priority < other.priority;  // 优先级高的任务优先处理
        }
        return id > other.id;  // 优先级相同时，编号小的任务优先处理
    }
};

int main() {
    int N;
    cin >> N;  // 读取事件数量
    cin.ignore();  // 消耗换行符

    vector<priority_queue<PrintJob>> printers(5);  // 初始化5个打印机队列
    int jobId = 1;  // 文件编号从1开始
    string command;
    int printerIndex;

    for (int i = 0; i < N; ++i) {
        cin >> command >> printerIndex;  // 读取命令和打印机编号
        printerIndex--;  // 将打印机编号转换为索引

        if (command == "IN") {
            int priority;
            cin >> priority;  // 读取任务优先级
            printers[printerIndex].push({priority, jobId++});  // 创建并加入新任务
        } else if (command == "OUT") {
            if (!printers[printerIndex].empty()) {
                cout << printers[printerIndex].top().id << endl;  // 输出任务编号
                printers[printerIndex].pop();  // 移除任务
            } else {
                cout << "NULL" << endl;  // 如果队列为空，输出"NULL"
            }
        }
    }

    return 0;
}

🏆下一篇：华为OD机试真题 - 简易内存池（Python/JS/C/C++ 2024 E卷 200分）

🏆本文收录于，华为OD机试真题（Python/JS/C/C++）

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

在这里插入图片描述


http://www.kler.cn/news/311164.html

相关文章：

  • 【分立元件】案例：新人加了个TVS管为什么可能导致系统不能正常工作
  • 【Unity】URP Rendering总结
  • 【C++STL简介】——我与C++的不解之缘（八）
  • 【PyTorch】深入浅出PyTorch
  • 模版进阶（template）
  • Java项目: 基于SpringBoot+mybatis+maven洗衣店订单管理系统(含源码+数据库+开题报告+任务书+毕业论文)
  • 【Flink Flick CDC】学习笔记
  • 架构设计 - 常用日志收集方案选型对比与推荐
  • 【java面试每日五题之基础篇一】（仅个人理解）
  • ACL 2024：交叉领域情感分析——论文阅读笔记
  • Kotlin cancel CoroutineScope.launch的任务后仍运行
  • PDF标准详解（五）——图形状态
  • 104. 二叉树的最大深度【 力扣(LeetCode) 】
  • VIM使用技巧
  • 从openAI最新模型GPT-o1再谈思维链(Cot)技术，大模型该怎么提升其逻辑推理能力？
  • 在 pika.SelectConnection 和 gevent 中实现高效异步：事件驱动与协程模型的冲突与优化
  • linux入门到实操-2 linux桌面、终端基本操作，文件系统、目录结构、挂载点
  • [数据集][目标检测]车窗状态检测车窗开关检测数据集VOC+YOLO格式299张3类别
  • CSS入门笔记
  • 【AI大模型-提示词的技巧】
  • python解析ip范围，拆分为所有ip数组
  • Qt快捷键说明与用法
  • 在Docker容器中执行命令
  • 数据湖-方案对比
  • ceph之osd扩容和缩容
  • 一个有个性的使用工具thefuck@Ubuntu
  • Java-list集合转成前端需要的json格式
  • 物理设计-理解与应用数据库范式于物理设计
  • 新能源汽车 BMS 学习笔记篇——N-MOS P-MOS 的开关原理及选型要点
  • redis基本数据结构-set