新卷-打印文件(C++ Python JAVA JS C语言)最佳实现-程序员充电站

题目描述:
有5台打印机打印文件，每台打印机有自己的待打印队列。因为打印的文件内容有轻重缓急之分，所以队列中的文件有1~10不同的优先级一，其中数字越大优先级越高。打印机会从自己的待打印队列中选择优先级最高的文件来打印。如果存在两个优先级一样的文件，则选择最早进入队列的那个文件。
现在请你来模拟这5台打印机的打印过程。
输入描述:每个输入包含1个测试用例一，每个测试用例第1行给出发生事件的数量N(O<N <1000)。接下来有N行，分别表示发生的事件。
共有如下两种事件:
1."N PNUM"，表示有一个拥有优先级NUM的文件放到了打印机Р的待打印队列中。(0<P <= 5,0<NUM<= 10);
2."OUTP"，表示打印机Р进行了一次文件打印，同时该文件从待打印队列中取出。(0<P <= 5)。输出描述:
对于每个测试用例，每次"OUTP"事件，请在一行中输出文件的编号。如果此时没有文件可以打印
请输
出"NULL"。
文件的编号定义为:"IN PNUM"事件发生第×次，此处待打印文件的编号为x。编号从1开始。

示例1

输入:
7
IN 1 1

IN 1 2

IN 1 3

IN 21

OUT 1

OUT 2

OUT 2
输出:
3

4
NULL

解题思路

需要模拟5台打印机的打印队列，处理两种事件：文件入队（IN）和打印出队（OUT）。对于OUT事件，需要从指定打印机的队列中取出优先级最高的文件（数字越大优先级越高），优先级相同时选择最早入队的文件。

关键步骤

数据结构选择：每台打印机使用一个优先队列（或普通队列+排序）来管理文件，队列中的元素需要记录文件的编号和优先级。
事件处理：根据输入的事件类型分别处理：
- IN事件：将文件加入对应打印机的队列，并记录文件编号。
- OUT事件：从对应打印机的队列中取出优先级最高的文件（或NULL）。
优先级处理：在队列中，优先级高的文件先出队，优先级相同时先入队的先出队。

代码实现

C++ 实现

使用优先队列（priority_queue）自定义排序规则：

#include <iostream> #include <queue> #include <vector> using namespace std; struct File { int id; int priority; int seq; // 入队顺序 }; struct Compare { bool operator()(const File& a, const File& b) { if (a.priority != b.priority) { return a.priority < b.priority; } return a.seq > b.seq; } }; int main() { int N; cin >> N; vector<priority_queue<File, vector<File>, Compare>> printers(5); int fileId = 1; for (int i = 0; i < N; ++i) { string op; cin >> op; if (op == "IN") { int p, num; cin >> p >> num; printers[p - 1].push({fileId, num, fileId}); fileId++; } else if (op == "OUT") { int p; cin >> p; if (!printers[p - 1].empty()) { File file = printers[p - 1].top(); printers[p - 1].pop(); cout << file.id << endl; } else { cout << "NULL" << endl; } } } return 0; }

Python 实现

使用堆（heapq）模拟优先队列：

import heapq class File: def __init__(self, id, priority, seq): self.id = id self.priority = priority self.seq = seq def __lt__(self, other): if self.priority != other.priority: return self.priority > other.priority return self.seq < other.seq def main(): N = int(input()) printers = [[] for _ in range(5)] file_id = 1 for _ in range(N): op = input().split() if op[0] == "IN": p = int(op[1]) - 1 num = int(op[2]) heapq.heappush(printers[p], File(file_id, num, file_id)) file_id += 1 elif op[0] == "OUT": p = int(op[1]) - 1 if printers[p]: file = heapq.heappop(printers[p]) print(file.id) else: print("NULL") if __name__ == "__main__": main()

Java 实现

使用PriorityQueue自定义排序：

import java.util.*; class File { int id; int priority; int seq; public File(int id, int priority, int seq) { this.id = id; this.priority = priority; this.seq = seq; } } public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); PriorityQueue<File>[] printers = new PriorityQueue[5]; for (int i = 0; i < 5; i++) { printers[i] = new PriorityQueue<>((a, b) -> { if (a.priority != b.priority) { return b.priority - a.priority; } return a.seq - b.seq; }); } int fileId = 1; for (int i = 0; i < N; i++) { String op = sc.next(); if (op.equals("IN")) { int p = sc.nextInt() - 1; int num = sc.nextInt(); printers[p].add(new File(fileId, num, fileId)); fileId++; } else if (op.equals("OUT")) { int p = sc.nextInt() - 1; if (!printers[p].isEmpty()) { File file = printers[p].poll(); System.out.println(file.id); } else { System.out.println("NULL"); } } } } }

JavaScript 实现

使用数组模拟优先队列：

class File { constructor(id, priority, seq) { this.id = id; this.priority = priority; this.seq = seq; } } function main() { const readline = require('readline'); const rl = readline.createInterface({ input: process.stdin, output: process.stdout, }); let N; const printers = Array.from({ length: 5 }, () => []); let fileId = 1; let lineCount = 0; rl.on('line', (line) => { if (lineCount === 0) { N = parseInt(line); lineCount++; } else { const parts = line.split(' '); const op = parts[0]; if (op === 'IN') { const p = parseInt(parts[1]) - 1; const num = parseInt(parts[2]); printers[p].push(new File(fileId, num, fileId)); fileId++; } else if (op === 'OUT') { const p = parseInt(parts[1]) - 1; if (printers[p].length > 0) { printers[p].sort((a, b) => { if (a.priority !== b.priority) { return b.priority - a.priority; } return a.seq - b.seq; }); const file = printers[p].shift(); console.log(file.id); } else { console.log('NULL'); } } lineCount++; if (lineCount > N) { rl.close(); } } }); } main();

C 实现

使用数组模拟优先队列：

#include <stdio.h> #include <string.h> typedef struct { int id; int priority; int seq; } File; File printers[5][1000]; int sizes[5] = {0}; int main() { int N; scanf("%d", &N); int fileId = 1; for (int i = 0; i < N; i++) { char op[5]; scanf("%s", op); if (strcmp(op, "IN") == 0) { int p, num; scanf("%d %d", &p, &num); printers[p - 1][sizes[p - 1]].id = fileId; printers[p - 1][sizes[p - 1]].priority = num; printers[p - 1][sizes[p - 1]].seq = fileId; sizes[p - 1]++; fileId++; } else if (strcmp(op, "OUT") == 0) { int p; scanf("%d", &p); if (sizes[p - 1] == 0) { printf("NULL\n"); continue; } int maxIdx = 0; for (int j = 1; j < sizes[p - 1]; j++) { if (printers[p - 1][j].priority > printers[p - 1][maxIdx].priority) { maxIdx = j; } else if (printers[p - 1][j].priority == printers[p - 1][maxIdx].priority) { if (printers[p - 1][j].seq < printers[p - 1][maxIdx].seq) { maxIdx = j; } } } printf("%d\n", printers[p - 1][maxIdx].id); for (int j = maxIdx; j < sizes[p - 1] - 1; j++) { printers[p - 1][j] = printers[p - 1][j + 1]; } sizes[p - 1]--; } } return 0; }