普通网站 seo 多少钱,公司企业名录大全,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
说明
无
题目解析
本题可以基于优先队列实现打印机总是打印优先级最高的文件。
优先队列如果想简单一点的话则可以基于有序数组实现但是有序数组是整体有序每次有新任务入队都需要O(n)时间复杂度维持。
优先队列最好是基于堆结构实现所谓堆结构即一颗完全二叉树。本题是优先级数值越大优先级越高因此我们可以使用大顶堆。
二、JavaScript算法源码
以下是基于有序数组实现优先队列的 JavaScript 代码的中文详细注释和逻辑讲解 代码逻辑
// 引入 readline 模块用于从控制台读取输入
const readline require(readline);// 创建 readline 接口
const rl readline.createInterface({input: process.stdin, // 输入流为标准输入output: process.stdout, // 输出流为标准输出
});// 存储输入行的数组
const lines [];
let n; // 存储任务的总数// 监听输入事件
rl.on(line, (line) {lines.push(line); // 将每一行输入存入 lines 数组// 如果输入的第一行是任务总数 nif (lines.length 1) {n parseInt(lines[0]); // 解析 n 为整数}// 如果输入的行数等于 n 1任务总数 任务内容if (n lines.length n 1) {lines.shift(); // 移除第一行任务总数// 将剩余的行解析为任务数组const tasks lines.map((line) line.split( ));// 调用算法函数处理任务getResult(tasks);// 清空 lines 数组准备接收下一组输入lines.length 0;}
});// 算法函数
function getResult(tasks) {// 使用对象存储每个打印机的任务队列const print {};// 任务 ID用于标识每个任务的唯一性let taskId 1;// 遍历所有任务for (let i 0; i tasks.length; i) {// 解析当前任务的类型、打印机 ID 和优先级const [type, printId, priority] tasks[i];// 如果是 IN 操作添加任务if (type IN) {// 创建一个任务数组包含任务 ID、优先级和任务顺序const arr [taskId, priority, i]; // i 是先来后到的顺序// 如果当前打印机 ID 不存在初始化一个空数组if (!print[printId]) {print[printId] []; // 基于数组实现优先队列}// 将任务添加到对应打印机的任务队列中print[printId].push(arr);// 对任务队列进行排序维持高优先级在头部// 如果优先级相同则按先来后到的顺序排序print[printId].sort((a, b) (a[1] ! b[1] ? b[1] - a[1] : a[2] - b[2]));// 任务 ID 自增taskId;}// 如果是 OUT 操作取出任务else {// 如果当前打印机 ID 不存在或任务队列为空输出 NULLif (!print[printId] || print[printId].length 0) {console.log(NULL);}// 否则取出队列中的第一个任务并输出任务 IDelse {const arr print[printId].shift(); // 移除队列中的第一个任务console.log(arr ? arr[0] : NULL); // 输出任务 ID}}}
}代码讲解 输入处理 使用 readline 模块从控制台读取输入。第一行输入为任务总数 n。后续 n 行输入为任务内容每行包含任务类型IN 或 OUT、打印机 ID 和优先级仅 IN 操作需要。 任务队列存储 使用对象 print 存储每个打印机的任务队列。每个打印机的任务队列是一个数组数组中的每个元素是一个任务包含任务 ID、优先级和任务顺序。 任务添加IN 操作 解析任务内容生成任务数组 [taskId, priority, i]其中 taskId任务的唯一标识。priority任务的优先级。i任务的顺序先来后到。 将任务添加到对应打印机的任务队列中。对任务队列进行排序优先级高的任务排在前面。如果优先级相同则按任务顺序排序。 任务取出OUT 操作 检查对应打印机的任务队列是否为空。如果队列为空输出 NULL。如果队列不为空取出队列中的第一个任务并输出任务 ID。 任务 ID 管理 使用 taskId 变量为每个任务分配唯一的 ID确保任务的唯一性。 排序逻辑 使用 sort 方法对任务队列进行排序 优先级高的任务排在前面b[1] - a[1]。如果优先级相同则按任务顺序排序a[2] - b[2]。 示例解析
输入
5
IN 1 10
IN 1 20
OUT 1
IN 1 30
OUT 1运行结果
2
3解析 第 1 个任务IN 1 10任务 ID 为 1优先级为 10。第 2 个任务IN 1 20任务 ID 为 2优先级为 20。第 3 个任务OUT 1取出打印机 1 的任务队列中的第一个任务优先级最高输出任务 ID 2。第 4 个任务IN 1 30任务 ID 为 3优先级为 30。第 5 个任务OUT 1取出打印机 1 的任务队列中的第一个任务优先级最高输出任务 ID 3。 总结
该代码基于有序数组实现了优先队列支持任务的添加和取出操作。通过排序逻辑确保高优先级任务优先处理同时支持任务顺序的优先级。适用于需要动态管理任务队列的场景如打印机任务调度等。
如果有其他问题欢迎随时提问
三、Java算法源码
以下是基于 Java 的 PriorityQueue 实现优先队列的代码的中文详细注释和逻辑讲解 代码逻辑
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.Scanner;public class Main {public static void main(String[] args) {// 创建 Scanner 对象用于从控制台读取输入Scanner sc new Scanner(System.in);// 读取任务总数 nint n Integer.parseInt(sc.nextLine());// 定义二维数组 tasks用于存储所有任务String[][] tasks new String[n][];// 读取 n 行任务内容并存入 tasks 数组for (int i 0; i n; i) {String[] s sc.nextLine().split( ); // 将每行输入按空格分割tasks[i] s; // 存入 tasks 数组}// 调用算法函数处理任务getResult(tasks);}public static void getResult(String[][] tasks) {// 使用 HashMap 存储每台打印机的等待队列// key: 打印机 IDvalue: 优先队列存储打印任务HashMapString, PriorityQueueint[] print new HashMap();// 文件编号从 1 开始int x 1;// 遍历所有任务for (int i 0; i tasks.length; i) {// 获取当前任务String[] task tasks[i];// 解析任务类型IN 或 OUT和打印机 IDString type task[0];String printId task[1];// 如果是 IN 操作添加任务if (IN.equals(type)) {// 解析任务的优先级String priority task[2];// 创建打印任务数组包含文件编号、优先级和任务顺序int[] arr {x, Integer.parseInt(priority), i}; // i 代表先来后到的顺序// 如果当前打印机 ID 不存在初始化一个优先队列print.putIfAbsent(printId,new PriorityQueue((a, b) -a[1] ! b[1] ? b[1] - a[1] : a[2] - b[2])); // 优先按优先级排序如果优先级相同按任务顺序排序// 将打印任务加入对应打印机的优先队列print.get(printId).offer(arr);// 文件编号自增x;}// 如果是 OUT 操作取出任务else {// 检查当前打印机的等待队列是否为空if (!print.containsKey(printId) || print.get(printId).isEmpty()) {// 如果队列为空输出 NULLSystem.out.println(NULL);} else {// 取出队列中优先级最高的任务int[] arr print.get(printId).poll();// 输出任务的文件编号if (arr ! null) System.out.println(arr[0]); // arr[0] 是文件编号 xelse System.out.println(NULL);}}}}
}代码讲解 输入处理 使用 Scanner 从控制台读取输入。第一行输入为任务总数 n。后续 n 行输入为任务内容每行包含任务类型IN 或 OUT、打印机 ID 和优先级仅 IN 操作需要。 任务队列存储 使用 HashMap 存储每台打印机的任务队列。HashMap 的 key 是打印机 IDvalue 是一个优先队列PriorityQueue用于存储打印任务。 任务添加IN 操作 解析任务内容生成任务数组 [x, priority, i]其中 x文件编号唯一标识任务。priority任务的优先级。i任务的顺序先来后到。 如果当前打印机 ID 不存在初始化一个优先队列并设置排序规则 优先级高的任务排在前面b[1] - a[1]。如果优先级相同则按任务顺序排序a[2] - b[2]。 将任务添加到对应打印机的优先队列中。 任务取出OUT 操作 检查对应打印机的任务队列是否为空。如果队列为空输出 NULL。如果队列不为空取出队列中优先级最高的任务并输出任务的文件编号。 文件编号管理 使用变量 x 为每个任务分配唯一的文件编号确保任务的唯一性。 优先队列排序规则 优先队列的排序规则通过 Comparator 实现 优先级高的任务排在前面。如果优先级相同则按任务顺序排序。 示例解析
输入
5
IN 1 10
IN 1 20
OUT 1
IN 1 30
OUT 1运行结果
2
3解析 第 1 个任务IN 1 10文件编号为 1优先级为 10。第 2 个任务IN 1 20文件编号为 2优先级为 20。第 3 个任务OUT 1取出打印机 1 的任务队列中的第一个任务优先级最高输出文件编号 2。第 4 个任务IN 1 30文件编号为 3优先级为 30。第 5 个任务OUT 1取出打印机 1 的任务队列中的第一个任务优先级最高输出文件编号 3。 总结
该代码基于 Java 的 PriorityQueue 实现了优先队列支持任务的添加和取出操作。通过自定义排序规则确保高优先级任务优先处理同时支持任务顺序的优先级。适用于需要动态管理任务队列的场景如打印机任务调度等。
如果有其他问题欢迎随时提问
四、Python算法源码
以下是基于 Python 的 queue.PriorityQueue 实现优先队列的代码的中文详细注释和逻辑讲解 代码逻辑
import queue# 输入获取
n int(input()) # 读取任务总数 ntasks [] # 定义列表 tasks用于存储所有任务
for i in range(n):tasks.append(input().split()) # 读取每行任务内容并存入 tasks 列表# 定义 Task 类用于表示打印任务
class Task:def __init__(self, taskId, priority, index):构造函数初始化任务对象:param taskId: 任务 ID:param priority: 任务优先级:param index: 任务到达顺序self.taskId taskIdself.priority priorityself.index indexdef __lt__(self, other):重载小于运算符定义任务的排序规则:param other: 另一个任务对象:return: 当前任务是否优先于另一个任务if self.priority ! other.priority:return self.priority other.priority # 优先级高的任务优先else:return self.index other.index # 如果优先级相同按任务到达顺序排序# 算法入口
def getResult(tasks):# 使用字典 printer 存储每台打印机的任务队列# key: 打印机 IDvalue: 优先队列存储 Task 对象printer {}# 任务 ID从 1 开始taskId 1# 遍历所有任务for i in range(len(tasks)):task tasks[i] # 获取当前任务# 解析任务类型IN 或 OUT和打印机 IDtype task[0]printerId task[1]# 如果是 IN 操作添加任务if type IN:# 解析任务的优先级priority task[2]# 如果当前打印机 ID 不存在初始化一个优先队列if printer.get(printerId) is None:printer[printerId] queue.PriorityQueue()# 创建 Task 对象表示当前任务t Task(taskId, int(priority), i)# 将任务加入对应打印机的优先队列printer[printerId].put(t)# 任务 ID 自增taskId 1# 如果是 OUT 操作取出任务else:# 检查当前打印机的任务队列是否为空if printer.get(printerId) is None or printer[printerId].qsize() 0:# 如果队列为空输出 NULLprint(NULL)else:# 取出队列中优先级最高的任务t printer[printerId].get()# 输出任务的任务 IDprint(t.taskId)# 调用算法函数处理任务
getResult(tasks)代码讲解 输入处理 使用 input() 函数从控制台读取输入。第一行输入为任务总数 n。后续 n 行输入为任务内容每行包含任务类型IN 或 OUT、打印机 ID 和优先级仅 IN 操作需要。 任务队列存储 使用字典 printer 存储每台打印机的任务队列。字典的 key 是打印机 IDvalue 是一个优先队列queue.PriorityQueue用于存储 Task 对象。 任务添加IN 操作 解析任务内容创建 Task 对象包含任务 ID、优先级和任务顺序。如果当前打印机 ID 不存在初始化一个优先队列。将任务添加到对应打印机的优先队列中。 任务取出OUT 操作 检查对应打印机的任务队列是否为空。如果队列为空输出 NULL。如果队列不为空取出队列中优先级最高的任务并输出任务的任务 ID。 任务排序规则 在 Task 类中重载 __lt__ 方法定义任务的排序规则 优先级高的任务优先self.priority other.priority。如果优先级相同则按任务到达顺序排序self.index other.index。 任务 ID 管理 使用变量 taskId 为每个任务分配唯一的任务 ID确保任务的唯一性。 示例解析
输入
5
IN 1 10
IN 1 20
OUT 1
IN 1 30
OUT 1运行结果
2
3解析 第 1 个任务IN 1 10任务 ID 为 1优先级为 10。第 2 个任务IN 1 20任务 ID 为 2优先级为 20。第 3 个任务OUT 1取出打印机 1 的任务队列中的第一个任务优先级最高输出任务 ID 2。第 4 个任务IN 1 30任务 ID 为 3优先级为 30。第 5 个任务OUT 1取出打印机 1 的任务队列中的第一个任务优先级最高输出任务 ID 3。 总结
该代码基于 Python 的 queue.PriorityQueue 实现了优先队列支持任务的添加和取出操作。通过重载 __lt__ 方法定义任务的排序规则确保高优先级任务优先处理同时支持任务顺序的优先级。适用于需要动态管理任务队列的场景如打印机任务调度等。
如果有其他问题欢迎随时提问
五、C/C算法源码
以下是基于 C 的 priority_queue 实现优先队列的代码的中文详细注释和逻辑讲解 代码逻辑
#include iostream
#include queue
#include vector
#include string
#include sstream
using namespace std;// 任务类
class Task {
public:int taskId; // 任务IDint priority; // 任务优先级int index; // 任务到达顺序// 构造函数初始化任务对象Task(int taskId, int priority, int index) : taskId(taskId), priority(priority), index(index) {}// 重载小于运算符用于优先队列的比较bool operator(const Task other) const {if (priority ! other.priority) {return priority other.priority; // 优先级高的排在前面} else {return index other.index; // 优先级相同先到的排在前面}}
};// 输入获取
int n; // 任务总数
vectorvectorstring tasks; // 存储所有任务的二维数组void readInput() {cin n; // 读取任务总数tasks.resize(n); // 调整 tasks 的大小为 nfor (int i 0; i n; i) {string line;cin line; // 读取每行任务内容stringstream ss(line); // 使用字符串流分割任务内容string token;while (ss token) {tasks[i].push_back(token); // 将分割后的任务内容存入 tasks}}
}// 算法入口
void getResult() {// 定义 6 个优先队列分别对应 6 个打印机编号 1-5vectorpriority_queueTask printer(6);// 任务 ID从 1 开始int taskId 1;// 遍历所有任务for (int i 0; i n; i) {const vectorstring task tasks[i]; // 获取当前任务// 解析任务类型IN 或 OUT和打印机 IDstring type task[0];int printerId stoi(task[1]);// 如果是 IN 操作添加任务if (type IN) {// 解析任务的优先级int priority stoi(task[2]);// 将任务加入对应打印机的优先队列printer[printerId].emplace(taskId, priority, i);// 任务 ID 自增taskId;}// 如果是 OUT 操作取出任务else {// 检查当前打印机的任务队列是否为空if (printer[printerId].empty()) {// 如果队列为空输出 NULLcout NULL endl;} else {// 取出队列中优先级最高的任务Task t printer[printerId].top();printer[printerId].pop();// 输出任务的任务 IDcout t.taskId endl;}}}
}int main() {readInput(); // 读取输入getResult(); // 处理任务return 0;
}代码讲解 输入处理 使用 cin 从控制台读取输入。第一行输入为任务总数 n。后续 n 行输入为任务内容每行包含任务类型IN 或 OUT、打印机 ID 和优先级仅 IN 操作需要。使用 stringstream 分割每行任务内容并存入二维数组 tasks。 任务队列存储 使用 vectorpriority_queueTask 存储 6 个打印机的任务队列编号 1-5。每个优先队列priority_queue存储 Task 对象。 任务添加IN 操作 解析任务内容创建 Task 对象包含任务 ID、优先级和任务顺序。将任务加入对应打印机的优先队列中。 任务取出OUT 操作 检查对应打印机的任务队列是否为空。如果队列为空输出 NULL。如果队列不为空取出队列中优先级最高的任务并输出任务的任务 ID。 任务排序规则 在 Task 类中重载 运算符定义任务的排序规则 优先级高的任务优先priority other.priority。如果优先级相同则按任务到达顺序排序index other.index。 任务 ID 管理 使用变量 taskId 为每个任务分配唯一的任务 ID确保任务的唯一性。 示例解析
输入
5
IN 1 10
IN 1 20
OUT 1
IN 1 30
OUT 1运行结果
2
3解析 第 1 个任务IN 1 10任务 ID 为 1优先级为 10。第 2 个任务IN 1 20任务 ID 为 2优先级为 20。第 3 个任务OUT 1取出打印机 1 的任务队列中的第一个任务优先级最高输出任务 ID 2。第 4 个任务IN 1 30任务 ID 为 3优先级为 30。第 5 个任务OUT 1取出打印机 1 的任务队列中的第一个任务优先级最高输出任务 ID 3。 总结
该代码基于 C 的 priority_queue 实现了优先队列支持任务的添加和取出操作。通过重载 运算符定义任务的排序规则确保高优先级任务优先处理同时支持任务顺序的优先级。适用于需要动态管理任务队列的场景如打印机任务调度等。
如果有其他问题欢迎随时提问
