上个月刷华为OD机试真题的时候遇到一道C卷的“打印机队列”题目本身不算特别难但非常典型它能把一个生活场景抽象成数据结构模型同时考到C语言里结构体、排序、队列、边界处理的基本功。如果你正在准备华为OD机试或者想用C语言练熟这类“模拟题”这道题值得从头到尾完整走一遍。下面我从题目形态、解题思路、可运行代码到机试现场那些坑一次性说清楚。1. 打印机队列这道题到底在考什么1.1 真题形态与样例还原不同批次的华为OD机试里“打印机队列”的题目描述会有小差别但内核基本一致。我刷到的C卷版本是这样的一台打印机需要处理一批打印任务。每个任务有两个属性任务编号id和优先级p。打印机每完成一个任务后从当前待打印任务中取出优先级最高的任务进行打印如果优先级相同则按照任务到达打印机队列的先后顺序先到的先打印。要求按实际打印顺序输出任务编号。输入格式通常是第一行一个整数 n表示任务总数。 接下来 n 行每行两个整数 id 和 p。输出格式就是一行按打印顺序输出所有任务id空格隔开。比如我给个自测样例输入 5 101 3 102 1 103 5 104 3 105 2按照规则103的优先级最高5第一个打印接下来101和104的优先级都是3但101先到所以101先打印104跟着然后是105优先级2最后是102优先级1。输出应该是103 101 104 105 102这个还原版本应该覆盖了大多数考场上的出题方式。有些变体会把优先级反过来数字越小优先级越高比如1级最高还有变体把任务编号范围扩大到10000。核心考察点不变多关键字排序优先级是主关键字到达顺序是次关键字。1.2 出题人想考察什么这道题在华为OD机试C卷里属于“数据结构模拟题”出题目的很明确看你能不能把一个实际问题抽象成数据模型并且用C语言正确实现。最直接的考察点有三个。第一你能不能看懂“优先级相同先到先打印”这句话并把它转化成排序条件或者选择条件。很多人只顾着按优先级排忘了处理同优先级顺序这在多关键字问题上是大忌。第二你对于队列和数组删除元素有没有清晰认识。原型里是“队列”但实际并不需要用队列去不停出队。这个抽象过程很关键——程序员的价值就是把复杂流程简化成可计算的模型。第三你的C语言基础扎不扎实。结构体怎么定义数组怎么遍历排序比较器怎么写变量初始化有没有漏这些细节只要有一个出错整道题就跑不对。所以这道题虽然叫“打印机队列”本质是一道“结构体排序/模拟选择题”。它不是难题但很能拉开分差。很多考生不是不会做而是掉进细节坑里导致提交后部分用例超时或者答案错误。2. 从任务调度规则到解题模型2.1 第一直觉把题目转成“每次取最大”的问题拿到题先别急着写代码先在草稿纸上把规则转成算法模型。打印机每次做什么它从所有“还没打印”的任务里挑出一个优先级最高的如果有并列挑到达顺序更早的那个。打印完这个任务就从集合里消失然后打印机继续下一个选择。这不就是一个“重复从集合中取出最大关键字元素”的过程吗整个过程重复n次直到任务全部打印完。所以模型是集合 所有未被打印的任务比较规则 先比prioritypriority大者优先priority相同比到达顺序先到者优先每次循环 找出符合条件的任务输出标志着它已打印然后排除。抽象成这个模型之后解法自然浮出水面。2.2 三种做法对比排序、扫描、二叉堆针对上面这个模型可以有三种实现路线。方案一直接排序。把n个任务当作一个结构体数组按“优先级降序到达顺序升序”排好序然后从头到尾输出id。这个做法利用的是“全排序一次搞定”的思路逻辑最简洁时间复杂度O(n log n)。方案二每轮扫描法。外层循环跑n次内层遍历当前数组找出优先级最高且未被打印的任务。找到后标记为已打印并输出。时间复杂度O(n^2)。方案三优先队列/二叉堆。读数据时建堆每次从堆顶取最大然后调整堆。这是数据结构和算法课程里的经典做法时间复杂度O(n log n)但手写堆代码量比较大。三种方案对比如下方案时间复杂度实现难度适用场景直接排序O(n log n)低qsort比较器要写对n很大时首选思路清晰每轮扫描法O(n^2)很低适合考试抢时间n在1000以内都可以二叉堆O(n log n)高需要手写堆和调整数据量极大或后续还要动态插入时我在机试现场选择的是“每轮扫描法”原因很简单题目里n的范围不会太大O(n^2)完全够用而这个做法不需要背堆的代码出错率最低。2.3 数据规模决定选型别一上来就背模板很多准备机试的同学有个习惯一看到“取最大值”就条件反射写堆看到“区间查询”就线段树。这个习惯在竞赛里没问题但在华为OD机试里可能适得其反。为什么因为机试要的是“在规定时间内拿到尽可能多的分”而不是“用最牛的数据结构炫技”。你的时间和精力是有限的手写一个二叉堆至少30行而且很容易在堆化、上浮下沉这些细节上出错。一旦错了一个边界条件整个数组顺序就乱套。我建议拿到题目后先估算数据规模。怎么估算看题目给的n上限和输入输出格式。如果n只有1000或者更小O(n^2)就是最稳的选择。外层循环1000次内层遍历1000次总共100万次操作C语言一秒钟能跑几十遍。这时候完全没必要用堆。如果n到了10^5甚至10^6O(n^2)就不行了10^5的平方是10^10肯定会超时。这时应该用排序或者堆。所以选型的核心依据是数据范围而不是个人偏好。在你没有十足把握手写堆的情况下优先选择那个你能一次写对、逻辑最不容易出错的方案。先把分拿到再去想更高级的优化这是机试里最务实的策略。3. C语言题解与关键代码3.1 结构体加标记法为什么这样设计既然选择“每轮扫描”接下来就是数据结构设计。这道题怎么存数据我用的结构体typedef struct { int id; // 任务编号 int priority; // 优先级 int used; // 标记是否已打印0未打印1已打印 } Job;id和priority是题目输入的used是我额外加的。它的作用非常关键——标记哪些任务已经“出队”。为什么不用真正的“删除元素”操作因为数组删除元素需要把后面的元素往前搬移每删除一次可能移动O(n)个元素代码也更复杂。而且题目并不要求维护“剩余任务”的实体只要逻辑上能把已打印任务排除掉就行。所以我用一个标记位来模拟“删除”这是典型的“逻辑删除”思路。实际扫描的时候遇到used为1的任务就跳过相当于它已经不在候选集合里了。这种写法简单而且不容易因为数组长度变化搞乱下标。3.2 完整的扫描法C代码下面是我在考场上写出来的版本加了注释方便你理解#include stdio.h #include string.h #define MAXN 1005 typedef struct { int id; int priority; int used; } Job; int main() { int n; // 华为OD机试一般是单组输入用 while(scanf(...)) 更保险 while (scanf(%d, n) ! EOF) { Job jobs[MAXN]; // 数组全部清零确保 used 初始为 0 memset(jobs, 0, sizeof(jobs)); for (int i 0; i n; i) { scanf(%d %d, jobs[i].id, jobs[i].priority); } // 总共打印 n 次每次找出一个任务 for (int i 0; i n; i) { int maxIdx -1; // 在所有未打印任务里找优先级最高的 for (int j 0; j n; j) { if (jobs[j].used) { continue; } if (maxIdx -1) { maxIdx j; continue; } // 只处理“严格大于”同优先级保持较早下标 j if (jobs[j].priority jobs[maxIdx].priority) { maxIdx j; } } // 输出当前选中的任务id // 用 %c 控制空格最后一项后输出换行避免行末空格 printf(%d%c, jobs[maxIdx].id, i n - 1 ? \n : ); jobs[maxIdx].used 1; } } return 0; }这段代码有几个地方值得单独说。第一个是maxIdx -1的处理。内层循环第一次找到未打印任务时直接把下标赋给maxIdx再往后遇到同样优先级的任务由于我只在priority 时更新maxIdx所以相同优先级情况下下标更靠前的任务会一直保留。这正好实现了“先到先打印”。第二个是输出格式。用printf(%d%c, jobs[maxIdx].id, i n - 1 ? \n : )如果当前是最后一个任务就打印换行否则打印空格。这样做的好处是没有行末空格很多严格校验输出的OJ不会报格式错。第三个是memset(jobs, 0, sizeof(jobs))。有些同学会在循环里手写for清零used但直接用memset更高效也避免漏掉某些字段。当然如果你觉得memset不好理解手写for也完全没问题for (int i 0; i n; i) { jobs[i].used 0; }两种写法效果一样关键是要记得初始化。3.3 qsort比较器版本与稳定性陷阱如果你在考场上一眼看出这题“排序”就能解决那用qsort也是很好的选择。但这里有一个非常隐蔽的坑我见过太多人掉进去。C语言标准库的qsort是不稳定的也就是说两个关键字相同的元素排序后的相对顺序不能保证和原来一样。这道题要求“优先级相同先到达的先打印”所以你必须把到达顺序也作为排序的次要关键字。怎么记录到达顺序直接用数组下标i就好我把它放进结构体里typedef struct { int id; int priority; int order; // 记录输入顺序也就是到达顺序 } Job;比较器这样写int cmp(const void *a, const void *b) { Job *x (Job *)a; Job *y (Job *)b; if (x-priority ! y-priority) { return y-priority - x-priority; // 优先级从大到小 } return x-order - y-order; // 到达顺序从小到大 }为什么不能只写return y-priority - x-priority因为这样处理不了优先级相同的情况。qsort可能把相同优先级的任务打乱打印顺序就错了。这里还有一个细节y-priority - x-priority这个写法只有在priority的取值范围远小于int范围时才安全。如果题目给priority特别大差值可能溢出稳妥一点可以写成if (x-priority ! y-priority) { return (x-priority y-priority) ? -1 : 1; }这种写法没有减法不会溢出也更清晰。排序版完整代码我就不重复贴了本质上就是把输入存进数组调用qsort再顺序输出。注意必须给每个元素赋值正确的order。4. 机试实战场双机位、ACM模式与常见失分点4.1 双机位机考环境要提前适应华为OD机试现在普遍采用双机位监考这是很多第一次参加线上机考的人会忽略的环境因素。所谓双机位一个是电脑端摄像头从正面拍到你、屏幕和桌面操作另一个是手机机位一般架在侧后方45度角覆盖你的全身、桌面和周围环境手机全程录像监考。这个双机位设置直接影响了你的备考方式。首先考前调试设备一定要做别等到考试开始才想起来手机支架没架好。手机要能拍到完整的桌面和你的手不能只露半个屏幕。摄像头测试的时候我建议实际打开会议软件看一眼画面确认没有死角。其次桌面上不要放和考试无关的东西。有些考场允许草稿纸和笔有些要求电子设备全部关机放远。草稿纸如果不是考场统一发的建议提前准备好并放在摄像头能看到的地方避免被判定违规。还有一个很实际的建议提前用这种监考模式做一次模拟练习。你只需要打开电脑摄像头再拿手机架到身后拍着自己掐着时间做一套题。看起来很简单但真到考试时候多一个手机在背后录你状态和平时单屏刷题完全不同。我第一次这样模拟时总是不自觉去看手机特别分心。提前适应一到两次考试心态会稳很多。4.2 ACM模式的输入输出习惯华为OD机试使用的是ACM模式要求你自己写完整程序包括main函数、输入读取和输出打印而不是像LeetCode那样只需要补全核心函数。很多习惯LeetCode的考生第一次接触ACM模式会非常不适应。ACM模式下C语言的输入输出是最容易出问题的地方。我总结几个实际高频坑。第一个坑是scanf读取失败。如果输入行里有额外的空白符、换行符只要格式控制符写得对scanf(%d %d, a, b)能自动跳过空白一般没问题。真正容易错的是用fgets读一行再sscanf解析一旦字符串末尾有多余空格或者回车解析可能出错。对于这种纯整数输入的题直接用scanf简单可靠。第二个坑是读入多组数据的问题。有些题目虽然没明说但OJ后台可能有多组测试样例。用while (scanf(%d, n) ! EOF)包裹既支持多组也不影响单组测试是更稳妥的写法。不过要注意在每组处理前重置数组状态。第三个坑是输出格式。行末不能多输出空格最后要换行。华为OJ对行末空格容忍度可能比其他OJ高但ACM小组赛和CCF等赛事对格式要求严格建议大家从第一天就养成严格输出的习惯。第四个坑是数组越界。任务编号范围可能很大但任务数量是有限的用数组存任务本身没问题。扫内层循环时一定要记得范围是[0, n)边界漏一个就可能导致漏输出一个任务或者访问非法内存。4.3 自测用例怎么设计无论你用的是排序法还是扫描法写完代码都不能直接提交。先在本地或者在线IDE跑一组自测用例把边界情况覆盖到。对于打印机队列这道题我建议至少准备下面几组测试。第一组是最基本的功能测试也就是题目样例输入 5 101 3 102 1 103 5 104 3 105 2期望输出103 101 104 105 102第二组测“同优先级先来先服务”。全部任务优先级设成一样这时打印顺序必须严格等于输入顺序输入 4 1 2 2 2 3 2 4 2 期望输出 1 2 3 4我见过不少人直接用qsort只排优先级这一组用例立刻把他们打回原形。第三组测“单个任务”这种最小规模输入 1 7 3期望输出就是7。这个用例同时还能验证空格处理对不对如果输出了多余空格或者没有换行一眼就能看出来。第四组测优先级全降序和全升序确认你的逻辑不会出现反序问题。比如输入 3 a 1 b 3 c 2 期望输出 b c a这些用例设计不需要很复杂关键是覆盖到单元素、全相同、逆序、乱序这四类情况。跑完这四组代码正确性就有八成把握了。5. 从打印机队列延伸出的复习建议5.1 这类模拟题在C卷里的地位华为OD机试C卷的题目结构并不是全是难题而是基础题、中等题、压轴题混合。打印机队列这类“模拟排序”的题通常出现在前几道属于兵家必争之地。它们的特点是读懂了就很简单读不懂或者踩了细节坑就会白白丢分。相比最后的动态规划或复杂搜索题这类题的性价比最高。你把这几道基础题全部拿下再加上一道中等题的思路整体分数就上去了。所以备考的时候不要只盯着难题刷。先把这类“模拟题”练熟它们能在考场上给你提供稳定的基本盘。打印机队列、旋转矩阵、括号匹配、字符串反转、链表删除这一类经典模拟题我建议在备考前期集中刷一遍每个都写到能一次通过的水平。5.2 我给C语言考生的刷题优先级如果你准备用C语言考华为OD机试我按自己的经验给你排一个优先级。第一优先级是掌握结构体与排序。qsort比较器、结构体数组、多关键字排序这是机试最高频的知识点之一打印机队列、成绩排序、榜单生成都靠它。必须做到闭着眼睛能写比较器。第二优先级是字符串处理。C语言的字符串没有现成的split需要自己用fgets、strtok、sscanf配合处理。很多题的输入都包含一行或多行字符串字符串处理不熟后面的逻辑再正确也白搭。第三优先级是基础数据结构栈、队列、链表、哈希表。机试里中等题经常是“基础数据结构 一个关键转换思路”的组合。第四优先级才轮得到DFS、BFS、动态规划、贪心这些算法。这些不是不重要而是准备顺序上应该放在前面三类之后。先把基础题稳定满分再考虑压轴题拿部分分。还有一个很多人忽略的点C语言的变量初始化。局部数组不初始化默认值是不确定的。如果used都从奇怪的值开始整个扫描逻辑立刻出错。我建议在代码开头统一memset或者手动清零别依赖编译器行为。5.3 复习节奏与真实考试体会在准备节奏上我不建议战线拉太长但也不建议裸考。比较合理的安排是花三到四周前两周集中过知识点和模块刷题第三周开始做整套真题模拟按考试时长要求自己逼自己在两小时内完成并调试通过。模拟考试一定要开着计时器因为真正的机试气氛和平时做题完全不一样第一题上卡十分钟后面就会很被动。我自己实际考试时的心态是先快速读一遍所有题目评估难度从自己最熟悉的模拟题和基础题开始做先确保AC两道题再回头啃难题的部分分。打印机队列这类题就是我优先稳固的基本盘之一。最后分享一个小技巧写代码前先在草稿纸上把样例手动模拟一遍。比如一支笔代表打印机另一支笔代表任务队列逐个标出优先级高的先打印同优先级按顺序。只要纸上模拟的结果和你脑海里算法一致写出来的代码通常不会跑偏。这道打印机队列能拿满分其实不是因为代码多漂亮而是因为我把“优先级相同看先后顺序”这个规则吃透了从一开始就没给失分留机会。
华为OD机试C卷真题解析：C语言实现打印机队列
上个月刷华为OD机试真题的时候遇到一道C卷的“打印机队列”题目本身不算特别难但非常典型它能把一个生活场景抽象成数据结构模型同时考到C语言里结构体、排序、队列、边界处理的基本功。如果你正在准备华为OD机试或者想用C语言练熟这类“模拟题”这道题值得从头到尾完整走一遍。下面我从题目形态、解题思路、可运行代码到机试现场那些坑一次性说清楚。1. 打印机队列这道题到底在考什么1.1 真题形态与样例还原不同批次的华为OD机试里“打印机队列”的题目描述会有小差别但内核基本一致。我刷到的C卷版本是这样的一台打印机需要处理一批打印任务。每个任务有两个属性任务编号id和优先级p。打印机每完成一个任务后从当前待打印任务中取出优先级最高的任务进行打印如果优先级相同则按照任务到达打印机队列的先后顺序先到的先打印。要求按实际打印顺序输出任务编号。输入格式通常是第一行一个整数 n表示任务总数。 接下来 n 行每行两个整数 id 和 p。输出格式就是一行按打印顺序输出所有任务id空格隔开。比如我给个自测样例输入 5 101 3 102 1 103 5 104 3 105 2按照规则103的优先级最高5第一个打印接下来101和104的优先级都是3但101先到所以101先打印104跟着然后是105优先级2最后是102优先级1。输出应该是103 101 104 105 102这个还原版本应该覆盖了大多数考场上的出题方式。有些变体会把优先级反过来数字越小优先级越高比如1级最高还有变体把任务编号范围扩大到10000。核心考察点不变多关键字排序优先级是主关键字到达顺序是次关键字。1.2 出题人想考察什么这道题在华为OD机试C卷里属于“数据结构模拟题”出题目的很明确看你能不能把一个实际问题抽象成数据模型并且用C语言正确实现。最直接的考察点有三个。第一你能不能看懂“优先级相同先到先打印”这句话并把它转化成排序条件或者选择条件。很多人只顾着按优先级排忘了处理同优先级顺序这在多关键字问题上是大忌。第二你对于队列和数组删除元素有没有清晰认识。原型里是“队列”但实际并不需要用队列去不停出队。这个抽象过程很关键——程序员的价值就是把复杂流程简化成可计算的模型。第三你的C语言基础扎不扎实。结构体怎么定义数组怎么遍历排序比较器怎么写变量初始化有没有漏这些细节只要有一个出错整道题就跑不对。所以这道题虽然叫“打印机队列”本质是一道“结构体排序/模拟选择题”。它不是难题但很能拉开分差。很多考生不是不会做而是掉进细节坑里导致提交后部分用例超时或者答案错误。2. 从任务调度规则到解题模型2.1 第一直觉把题目转成“每次取最大”的问题拿到题先别急着写代码先在草稿纸上把规则转成算法模型。打印机每次做什么它从所有“还没打印”的任务里挑出一个优先级最高的如果有并列挑到达顺序更早的那个。打印完这个任务就从集合里消失然后打印机继续下一个选择。这不就是一个“重复从集合中取出最大关键字元素”的过程吗整个过程重复n次直到任务全部打印完。所以模型是集合 所有未被打印的任务比较规则 先比prioritypriority大者优先priority相同比到达顺序先到者优先每次循环 找出符合条件的任务输出标志着它已打印然后排除。抽象成这个模型之后解法自然浮出水面。2.2 三种做法对比排序、扫描、二叉堆针对上面这个模型可以有三种实现路线。方案一直接排序。把n个任务当作一个结构体数组按“优先级降序到达顺序升序”排好序然后从头到尾输出id。这个做法利用的是“全排序一次搞定”的思路逻辑最简洁时间复杂度O(n log n)。方案二每轮扫描法。外层循环跑n次内层遍历当前数组找出优先级最高且未被打印的任务。找到后标记为已打印并输出。时间复杂度O(n^2)。方案三优先队列/二叉堆。读数据时建堆每次从堆顶取最大然后调整堆。这是数据结构和算法课程里的经典做法时间复杂度O(n log n)但手写堆代码量比较大。三种方案对比如下方案时间复杂度实现难度适用场景直接排序O(n log n)低qsort比较器要写对n很大时首选思路清晰每轮扫描法O(n^2)很低适合考试抢时间n在1000以内都可以二叉堆O(n log n)高需要手写堆和调整数据量极大或后续还要动态插入时我在机试现场选择的是“每轮扫描法”原因很简单题目里n的范围不会太大O(n^2)完全够用而这个做法不需要背堆的代码出错率最低。2.3 数据规模决定选型别一上来就背模板很多准备机试的同学有个习惯一看到“取最大值”就条件反射写堆看到“区间查询”就线段树。这个习惯在竞赛里没问题但在华为OD机试里可能适得其反。为什么因为机试要的是“在规定时间内拿到尽可能多的分”而不是“用最牛的数据结构炫技”。你的时间和精力是有限的手写一个二叉堆至少30行而且很容易在堆化、上浮下沉这些细节上出错。一旦错了一个边界条件整个数组顺序就乱套。我建议拿到题目后先估算数据规模。怎么估算看题目给的n上限和输入输出格式。如果n只有1000或者更小O(n^2)就是最稳的选择。外层循环1000次内层遍历1000次总共100万次操作C语言一秒钟能跑几十遍。这时候完全没必要用堆。如果n到了10^5甚至10^6O(n^2)就不行了10^5的平方是10^10肯定会超时。这时应该用排序或者堆。所以选型的核心依据是数据范围而不是个人偏好。在你没有十足把握手写堆的情况下优先选择那个你能一次写对、逻辑最不容易出错的方案。先把分拿到再去想更高级的优化这是机试里最务实的策略。3. C语言题解与关键代码3.1 结构体加标记法为什么这样设计既然选择“每轮扫描”接下来就是数据结构设计。这道题怎么存数据我用的结构体typedef struct { int id; // 任务编号 int priority; // 优先级 int used; // 标记是否已打印0未打印1已打印 } Job;id和priority是题目输入的used是我额外加的。它的作用非常关键——标记哪些任务已经“出队”。为什么不用真正的“删除元素”操作因为数组删除元素需要把后面的元素往前搬移每删除一次可能移动O(n)个元素代码也更复杂。而且题目并不要求维护“剩余任务”的实体只要逻辑上能把已打印任务排除掉就行。所以我用一个标记位来模拟“删除”这是典型的“逻辑删除”思路。实际扫描的时候遇到used为1的任务就跳过相当于它已经不在候选集合里了。这种写法简单而且不容易因为数组长度变化搞乱下标。3.2 完整的扫描法C代码下面是我在考场上写出来的版本加了注释方便你理解#include stdio.h #include string.h #define MAXN 1005 typedef struct { int id; int priority; int used; } Job; int main() { int n; // 华为OD机试一般是单组输入用 while(scanf(...)) 更保险 while (scanf(%d, n) ! EOF) { Job jobs[MAXN]; // 数组全部清零确保 used 初始为 0 memset(jobs, 0, sizeof(jobs)); for (int i 0; i n; i) { scanf(%d %d, jobs[i].id, jobs[i].priority); } // 总共打印 n 次每次找出一个任务 for (int i 0; i n; i) { int maxIdx -1; // 在所有未打印任务里找优先级最高的 for (int j 0; j n; j) { if (jobs[j].used) { continue; } if (maxIdx -1) { maxIdx j; continue; } // 只处理“严格大于”同优先级保持较早下标 j if (jobs[j].priority jobs[maxIdx].priority) { maxIdx j; } } // 输出当前选中的任务id // 用 %c 控制空格最后一项后输出换行避免行末空格 printf(%d%c, jobs[maxIdx].id, i n - 1 ? \n : ); jobs[maxIdx].used 1; } } return 0; }这段代码有几个地方值得单独说。第一个是maxIdx -1的处理。内层循环第一次找到未打印任务时直接把下标赋给maxIdx再往后遇到同样优先级的任务由于我只在priority 时更新maxIdx所以相同优先级情况下下标更靠前的任务会一直保留。这正好实现了“先到先打印”。第二个是输出格式。用printf(%d%c, jobs[maxIdx].id, i n - 1 ? \n : )如果当前是最后一个任务就打印换行否则打印空格。这样做的好处是没有行末空格很多严格校验输出的OJ不会报格式错。第三个是memset(jobs, 0, sizeof(jobs))。有些同学会在循环里手写for清零used但直接用memset更高效也避免漏掉某些字段。当然如果你觉得memset不好理解手写for也完全没问题for (int i 0; i n; i) { jobs[i].used 0; }两种写法效果一样关键是要记得初始化。3.3 qsort比较器版本与稳定性陷阱如果你在考场上一眼看出这题“排序”就能解决那用qsort也是很好的选择。但这里有一个非常隐蔽的坑我见过太多人掉进去。C语言标准库的qsort是不稳定的也就是说两个关键字相同的元素排序后的相对顺序不能保证和原来一样。这道题要求“优先级相同先到达的先打印”所以你必须把到达顺序也作为排序的次要关键字。怎么记录到达顺序直接用数组下标i就好我把它放进结构体里typedef struct { int id; int priority; int order; // 记录输入顺序也就是到达顺序 } Job;比较器这样写int cmp(const void *a, const void *b) { Job *x (Job *)a; Job *y (Job *)b; if (x-priority ! y-priority) { return y-priority - x-priority; // 优先级从大到小 } return x-order - y-order; // 到达顺序从小到大 }为什么不能只写return y-priority - x-priority因为这样处理不了优先级相同的情况。qsort可能把相同优先级的任务打乱打印顺序就错了。这里还有一个细节y-priority - x-priority这个写法只有在priority的取值范围远小于int范围时才安全。如果题目给priority特别大差值可能溢出稳妥一点可以写成if (x-priority ! y-priority) { return (x-priority y-priority) ? -1 : 1; }这种写法没有减法不会溢出也更清晰。排序版完整代码我就不重复贴了本质上就是把输入存进数组调用qsort再顺序输出。注意必须给每个元素赋值正确的order。4. 机试实战场双机位、ACM模式与常见失分点4.1 双机位机考环境要提前适应华为OD机试现在普遍采用双机位监考这是很多第一次参加线上机考的人会忽略的环境因素。所谓双机位一个是电脑端摄像头从正面拍到你、屏幕和桌面操作另一个是手机机位一般架在侧后方45度角覆盖你的全身、桌面和周围环境手机全程录像监考。这个双机位设置直接影响了你的备考方式。首先考前调试设备一定要做别等到考试开始才想起来手机支架没架好。手机要能拍到完整的桌面和你的手不能只露半个屏幕。摄像头测试的时候我建议实际打开会议软件看一眼画面确认没有死角。其次桌面上不要放和考试无关的东西。有些考场允许草稿纸和笔有些要求电子设备全部关机放远。草稿纸如果不是考场统一发的建议提前准备好并放在摄像头能看到的地方避免被判定违规。还有一个很实际的建议提前用这种监考模式做一次模拟练习。你只需要打开电脑摄像头再拿手机架到身后拍着自己掐着时间做一套题。看起来很简单但真到考试时候多一个手机在背后录你状态和平时单屏刷题完全不同。我第一次这样模拟时总是不自觉去看手机特别分心。提前适应一到两次考试心态会稳很多。4.2 ACM模式的输入输出习惯华为OD机试使用的是ACM模式要求你自己写完整程序包括main函数、输入读取和输出打印而不是像LeetCode那样只需要补全核心函数。很多习惯LeetCode的考生第一次接触ACM模式会非常不适应。ACM模式下C语言的输入输出是最容易出问题的地方。我总结几个实际高频坑。第一个坑是scanf读取失败。如果输入行里有额外的空白符、换行符只要格式控制符写得对scanf(%d %d, a, b)能自动跳过空白一般没问题。真正容易错的是用fgets读一行再sscanf解析一旦字符串末尾有多余空格或者回车解析可能出错。对于这种纯整数输入的题直接用scanf简单可靠。第二个坑是读入多组数据的问题。有些题目虽然没明说但OJ后台可能有多组测试样例。用while (scanf(%d, n) ! EOF)包裹既支持多组也不影响单组测试是更稳妥的写法。不过要注意在每组处理前重置数组状态。第三个坑是输出格式。行末不能多输出空格最后要换行。华为OJ对行末空格容忍度可能比其他OJ高但ACM小组赛和CCF等赛事对格式要求严格建议大家从第一天就养成严格输出的习惯。第四个坑是数组越界。任务编号范围可能很大但任务数量是有限的用数组存任务本身没问题。扫内层循环时一定要记得范围是[0, n)边界漏一个就可能导致漏输出一个任务或者访问非法内存。4.3 自测用例怎么设计无论你用的是排序法还是扫描法写完代码都不能直接提交。先在本地或者在线IDE跑一组自测用例把边界情况覆盖到。对于打印机队列这道题我建议至少准备下面几组测试。第一组是最基本的功能测试也就是题目样例输入 5 101 3 102 1 103 5 104 3 105 2期望输出103 101 104 105 102第二组测“同优先级先来先服务”。全部任务优先级设成一样这时打印顺序必须严格等于输入顺序输入 4 1 2 2 2 3 2 4 2 期望输出 1 2 3 4我见过不少人直接用qsort只排优先级这一组用例立刻把他们打回原形。第三组测“单个任务”这种最小规模输入 1 7 3期望输出就是7。这个用例同时还能验证空格处理对不对如果输出了多余空格或者没有换行一眼就能看出来。第四组测优先级全降序和全升序确认你的逻辑不会出现反序问题。比如输入 3 a 1 b 3 c 2 期望输出 b c a这些用例设计不需要很复杂关键是覆盖到单元素、全相同、逆序、乱序这四类情况。跑完这四组代码正确性就有八成把握了。5. 从打印机队列延伸出的复习建议5.1 这类模拟题在C卷里的地位华为OD机试C卷的题目结构并不是全是难题而是基础题、中等题、压轴题混合。打印机队列这类“模拟排序”的题通常出现在前几道属于兵家必争之地。它们的特点是读懂了就很简单读不懂或者踩了细节坑就会白白丢分。相比最后的动态规划或复杂搜索题这类题的性价比最高。你把这几道基础题全部拿下再加上一道中等题的思路整体分数就上去了。所以备考的时候不要只盯着难题刷。先把这类“模拟题”练熟它们能在考场上给你提供稳定的基本盘。打印机队列、旋转矩阵、括号匹配、字符串反转、链表删除这一类经典模拟题我建议在备考前期集中刷一遍每个都写到能一次通过的水平。5.2 我给C语言考生的刷题优先级如果你准备用C语言考华为OD机试我按自己的经验给你排一个优先级。第一优先级是掌握结构体与排序。qsort比较器、结构体数组、多关键字排序这是机试最高频的知识点之一打印机队列、成绩排序、榜单生成都靠它。必须做到闭着眼睛能写比较器。第二优先级是字符串处理。C语言的字符串没有现成的split需要自己用fgets、strtok、sscanf配合处理。很多题的输入都包含一行或多行字符串字符串处理不熟后面的逻辑再正确也白搭。第三优先级是基础数据结构栈、队列、链表、哈希表。机试里中等题经常是“基础数据结构 一个关键转换思路”的组合。第四优先级才轮得到DFS、BFS、动态规划、贪心这些算法。这些不是不重要而是准备顺序上应该放在前面三类之后。先把基础题稳定满分再考虑压轴题拿部分分。还有一个很多人忽略的点C语言的变量初始化。局部数组不初始化默认值是不确定的。如果used都从奇怪的值开始整个扫描逻辑立刻出错。我建议在代码开头统一memset或者手动清零别依赖编译器行为。5.3 复习节奏与真实考试体会在准备节奏上我不建议战线拉太长但也不建议裸考。比较合理的安排是花三到四周前两周集中过知识点和模块刷题第三周开始做整套真题模拟按考试时长要求自己逼自己在两小时内完成并调试通过。模拟考试一定要开着计时器因为真正的机试气氛和平时做题完全不一样第一题上卡十分钟后面就会很被动。我自己实际考试时的心态是先快速读一遍所有题目评估难度从自己最熟悉的模拟题和基础题开始做先确保AC两道题再回头啃难题的部分分。打印机队列这类题就是我优先稳固的基本盘之一。最后分享一个小技巧写代码前先在草稿纸上把样例手动模拟一遍。比如一支笔代表打印机另一支笔代表任务队列逐个标出优先级高的先打印同优先级按顺序。只要纸上模拟的结果和你脑海里算法一致写出来的代码通常不会跑偏。这道打印机队列能拿满分其实不是因为代码多漂亮而是因为我把“优先级相同看先后顺序”这个规则吃透了从一开始就没给失分留机会。
