华为OD机试：打印机队列调度算法与实现

1. 项目背景与核心需求解析打印机队列问题在操作系统和实际工程中都是一个经典场景。华为OD机试选择这个题目作为C卷考核点主要考察候选人对以下核心能力的掌握多任务调度理解现代操作系统中的打印服务需要处理来自不同用户的并发请求数据结构应用队列(Queue)的基本特性与变种实现边界条件处理异常输入、优先级冲突等现实场景问题双机位协同分布式环境下任务同步的初级解决方案这个题目在ACM/LeetCode中对应的原型是Priority Queue with Simulation类问题但华为OD的版本特别增加了双物理打印机的硬件限制条件中文自然语言描述的输入输出格式需要处理的中文编码问题GB18030/UTF-8转换2. 解题思路与算法设计2.1 基础队列模型最朴素的解决方案是使用两个先进先出(FIFO)队列#define MAX_QUEUE_SIZE 100 typedef struct { int job_id; int priority; char user[32]; } PrintJob; PrintJob printer1[MAX_QUEUE_SIZE]; PrintJob printer2[MAX_QUEUE_SIZE]; int front1 0, rear1 0; int front2 0, rear2 0;但这种设计无法处理以下关键需求高优先级任务插队打印机故障时的任务转移用户取消打印请求2.2 增强型优先队列方案改进方案采用最大堆(MAX Heap)实现优先级调度typedef struct { PrintJob jobs[MAX_QUEUE_SIZE]; int size; } PriorityQueue; void heapify_up(PriorityQueue *q, int index) { while (index 0 q-jobs[index].priority q-jobs[(index-1)/2].priority) { swap(q-jobs[index], q-jobs[(index-1)/2]); index (index-1)/2; } }2.3 双机位负载均衡策略当两个打印机都可用时需要智能分配任务。实测效果最好的策略是维护全局等待队列当打印机空闲时从队列头部取任务如果任务优先级阈值直接分配给最先空闲的打印机否则采用轮询(Round-Robin)分配void dispatch_job(GlobalQueue *gq, Printer *p1, Printer *p2) { if (gq-size 0) return; PrintJob job gq-jobs[gq-front]; if (job.priority PRIORITY_THRESHOLD) { if (p1-status IDLE) assign_to_printer(p1, job); else assign_to_printer(p2, job); } else { static int last_used 0; if (last_used 0 p1-status IDLE) { assign_to_printer(p1, job); last_used 1; } else if (p2-status IDLE) { assign_to_printer(p2, job); last_used 0; } } }3. 关键实现细节3.1 输入输出处理华为OD的输入通常是多行字符串需要特别注意第一行是整数N1≤N≤100表示任务数量后续N行每行格式为任务ID 优先级 用户名优先级范围1-9数字越大优先级越高void parse_input() { char line[256]; fgets(line, sizeof(line), stdin); int n atoi(line); for (int i 0; i n; i) { fgets(line, sizeof(line), stdin); char *token strtok(line, ); int job_id atoi(token); token strtok(NULL, ); int priority atoi(token); token strtok(NULL, \n); char user[32]; strncpy(user, token, 31); add_job(job_id, priority, user); } }3.2 线程安全实现虽然C卷不强制要求多线程但优秀实现应该考虑使用互斥锁保护共享队列条件变量实现生产者-消费者模型原子操作更新状态标志pthread_mutex_t queue_mutex PTHREAD_MUTEX_INITIALIZER; pthread_cond_t queue_cond PTHREAD_COND_INITIALIZER; void* printer_thread(void *arg) { Printer *p (Printer*)arg; while (1) { pthread_mutex_lock(queue_mutex); while (global_queue.size 0) { pthread_cond_wait(queue_cond, queue_mutex); } PrintJob job get_job_from_queue(); pthread_mutex_unlock(queue_mutex); print_document(p, job); } return NULL; }4. 测试用例与调试技巧4.1 必须覆盖的测试场景边界测试单任务提交队列满时提交新任务所有任务优先级相同异常测试无效优先级输入空用户名任务ID重复性能测试100个任务连续提交高优先级任务晚到场景一个打印机故障时的容错4.2 华为OD评判标准根据考生反馈评分重点在于输出结果的正确性60%代码结构清晰度20%边界条件处理15%注释和可读性5%特别注意华为OD环境会自动添加\r字符建议在字符串处理时先执行trim操作void trim_crlf(char *str) { char *p strchr(str, \r); if (p) *p \0; p strchr(str, \n); if (p) *p \0; }5. 性能优化方案5.1 内存管理优化避免频繁malloc/free的三种策略预分配任务数组池使用内存arena模式对象复用技术#define POOL_SIZE 200 PrintJob job_pool[POOL_SIZE]; int pool_index 0; PrintJob* alloc_job() { if (pool_index POOL_SIZE) return NULL; return job_pool[pool_index]; }5.2 调度算法优化原始优先级队列的O(logN)插入时间复杂度可以优化当新任务优先级当前最小优先级时直接插入尾部O(1)批量插入时先排序再合并O(N) for N itemsvoid smart_insert(PriorityQueue *q, PrintJob job) { if (q-size 0 || job.priority q-jobs[q-size-1].priority) { q-jobs[q-size] job; } else { // 标准堆插入 q-jobs[q-size] job; heapify_up(q, q-size); q-size; } }6. 扩展思考与实际应用6.1 工业级打印系统的差异真实打印系统还需考虑打印作业的暂停/继续纸张类型匹配检查用户权限验证打印内容预解析6.2 其他应用场景类似的队列管理模型也适用于餐厅订单系统医院挂号分诊物流包裹分拣云计算任务调度我在实际开发中遇到过的一个坑是没有考虑打印机离线时任务的保存和恢复。后来改进的方案是定期将队列状态持久化到SQLite数据库并在系统启动时恢复void save_queue_to_db() { sqlite3 *db; sqlite3_open(print_queue.db, db); sqlite3_exec(db, BEGIN TRANSACTION, NULL, NULL, NULL); sqlite3_exec(db, DELETE FROM pending_jobs, NULL, NULL, NULL); for (int i 0; i queue.size; i) { char sql[512]; snprintf(sql, sizeof(sql), INSERT INTO pending_jobs VALUES(%d, %d, %s), queue.jobs[i].job_id, queue.jobs[i].priority, queue.jobs[i].user); sqlite3_exec(db, sql, NULL, NULL, NULL); } sqlite3_exec(db, COMMIT, NULL, NULL, NULL); sqlite3_close(db); }