华为机试C卷备考：任务编排最早完成时间算法解析

准备华为机试那段时间我最大的感受是编程模拟题和真正上机考试是两码事。尤其现在华为OD机试换成了新系统双机位C卷的讨论越来越多很多人还在按老办法背题、刷题库结果一上机就被输入输出打懵。这篇博文不列什么“内部题库全集”我就用一道我自己改编过的模拟题——任务编排的最早完成时间完整走一遍从读题、建模、写码到复盘的全过程顺便聊聊C卷新系统下更值得关注的算法考点和备考方式。如果你正在准备华为机试、华为OD机试或者单纯想练算法这篇文章都适合。尤其是那种“网上真题刷了很多但一到ACM模式就手生”的人建议花二十分钟把这道题亲手做一遍比刷十道水题有用得多。1. 双机位C卷时代备考思路要先校准1.1 新系统最大的变化ACM模式回归过去很多人准备机试时习惯了在力扣式IDE里写函数系统已经把参数封装好只需要补全内部逻辑。但华为机试的新系统不是这样它更接近ACM模式题目只给输入输出描述你需要自己写完整的程序自己读标准输入、解析数据、输出结果。这个变化影响非常大。哪怕算法思路完全正确如果输入解析写错样例都过不了。更现实的是机试系统不会像本地IDE一样给你智能提示很多快捷键、代码补全、自动导入都不存在。平时依赖IDE的人第一次上机光是手写import sys和sys.stdin.read()都会愣几秒。所以我一直建议备考阶段必须用“最朴素的Python/Java环境”做题不要开代码补全不要用自动格式化。习惯裸写输入输出解析上机时才不会因为工具差异手忙脚乱。1.2 双机位带来的节奏变化新系统普遍采用双机位监考电脑摄像头拍正面手机在侧面或者后方拍整个桌面。这意味着考试过程中你基本上不能离开座位也不能频繁低头看手机。单纯从技术角度讲双机位对题目难度没有影响但它会实实在在影响你的答题节奏。比如有些同学习惯先打开编辑器跑个简单print测试环境再写正式代码。双机位下这种试探没有意义反而显得可疑。更合理的做法是先读题想清楚数据结构和算法再一次性写出完整代码最后用题目给的样例自测。我自己的经验是上机前把摄像头、手机支架、网络都提前调整好开考前就不要去碰设备了。考试中把所有精力放在“读题、建模、编码、验证”这四个环节上不做任何多余操作节奏会稳很多。1.3 刷题库的正确姿势现在网上关于“华为OD机试真题题库”的内容很多CSDN上甚至能看到按卷整理的目录和算法考点说明比如C卷、D卷的题单很多还是热心人同步的回忆版。这些资料有价值但有一个坑相当一部分题目是考后回忆输入输出格式可能和原题有出入甚至样例都记错了。如果抱着“背题”的心态去刷一碰到题目措辞变化就会露馅。机试真正考察的是把一个实际问题抽象成算法模型的能力。题库只是素材库不是标准答案库。我更喜欢把每一道题都做一次“考点映射”这道题到底在考哪个数据结构是动态规划、贪心、图论还是字符串模拟如果把题目里的业务名称换成通用术语它还剩下什么这个过程比刷题本身更重要。带着这套思路去刷题50道题的效果可能超过别人盲目刷新200道。2. 一道模拟题拆解任务编排的最早完成时间2.1 题目描述我用的这道模拟题综合了图论、拓扑排序、动态规划和字符串解析非常贴近C卷的现实命题风格。题目是我根据常见项目调度场景改写的不是原题但考点完全对标。有一个项目包含若干任务任务之间存在依赖关系。每个任务都有唯一ID和固定耗时。只有在它依赖的所有任务都完成后该任务才能开始。现在假设可用机器数量足够多互不依赖的任务可以同时执行。给定所有任务信息和依赖关系求整个项目最早能在什么时间全部完成。如果任务依赖关系存在环导致任务无法完成则输出-1。输入格式 第一行一个正整数n表示任务总数1 n 1000。 接下来n行每行表示一个任务任务ID 任务耗时 依赖任务列表其中任务ID是不含空格的字符串任务耗时是1到100之间的整数依赖任务列表由若干个任务ID组成用英文逗号分隔如果任务没有任何依赖依赖任务列表用单个短横线-表示。输出格式 一个整数表示最早完成全部任务的时间若存在循环依赖则输出-1。这道题拿到手先别急着写代码。先看几个关键点任务ID是字符串不是数字下标依赖列表可能为空多个任务可以并行存在环要输出-1。这几条几乎每一条都能让没经验的人翻车。2.2 样例推演样例15 A 5 - B 3 A C 4 A,B D 2 A E 6 C,D推演过程A没有依赖耗时5所以A的最早完成时间是5。B依赖AA在第5时间点完成B耗时3所以B最早完成时间是8。D依赖AA在第5时间点完成D耗时2所以D最早完成时间是7。C依赖A和BA完成时间是5B完成时间是8取最晚的8作为C的开始时间C耗时4所以C最早完成时间是12。E依赖C和DC完成时间是12D完成时间是7取最晚的12E耗时6所以E最早完成时间是18。最终所有任务完成时间是18。这里最容易错的是C和E的开始时间。C虽然写依赖了A和B但A早就完成了真正卡脖子的是BE卡脖子的则是C。不是简单把所有依赖任务的耗时加起来而是要在所有依赖任务里“取最晚的完成时间”。样例22 A 2 B B 3 AA依赖BB依赖A形成循环依赖两个任务永远无法开始输出-1。这个样例看着简单但循环依赖的判断很考验对拓扑排序的理解。2.3 这道题的真实考点表面上看这是一个“项目调度”业务题。剥掉外壳核心其实是一道“有向无环图上的最长路径”问题每个任务是一个节点如果任务v依赖任务u就存在一条从u指向v的有向边边的权重是任务u的耗时要求从任意入度为0的节点出发到每个节点的最长路径为什么是最长路径而不是最短路径因为一个任务必须等它所有前驱任务都完成才能开始所以它的最早开始时间取决于“最慢的那个前驱”也就是所有前驱完成时间的最大值。这道题同时考了三个能力建模能力能不能把依赖关系转化成一张有向图算法能力知不知道用拓扑排序处理DAG并用动态规划思想更新状态工程能力能不能正确解析字符串、处理输入输出、处理字符串ID和-空依赖。C卷很多题目都是这样一个综合体。它不考偏题怪题但会在看似普通的模型上叠加各种工程细节。3. 从题意到算法拓扑排序与最长路径建模3.1 为什么直接模拟耗时总和是错的我第一次做类似题时第一反应是“把每条依赖链上的耗时加起来取最大值”。后来发现这个思路不够严谨因为它默认了一条链走到黑忽略了并行和汇聚。看样例1依赖链A-C-E的总耗时是54615但答案是18。原因在于E还卡了C和DC完成之前E不能开始而D那条分支虽然早完成却不会拖慢E。最长路径并不是单一依赖链的简单累加而是要考虑所有前驱节点完成时间的最大值。换个更生活化的例子你要同时等水电工和木工干完才能刷墙。水电工耗时3天木工耗时5天刷墙耗时2天。刷墙最早开始时间是第5天不是第3天最终完成时间是7天不是35210天。这个“取所有前驱完成时间的最大值”就是状态转移的关键。3.2 状态设计每个任务的最早完成时间先定义状态finish[u]任务u的最早完成时间。如果任务u没有任何依赖finish[u] duration[u]如果任务u有多个依赖任务p1, p2, ..., pkfinish[u] max(finish[p1], finish[p2], ..., finish[pk]) duration[u]整个项目的最早完成时间是所有finish[u]的最大值。注意不是最后一个出队节点的完成时间因为拓扑排序的出队顺序取决于队列结构最后一个出队的节点不一定就是完成时间最晚的节点。这种状态设计本质上是动态规划但它不能直接递归求解。原因是任务之间存在依赖直接DFS会导致大量重复计算而且无法优雅地处理环。更稳妥的做法是用拓扑排序保证求解顺序只有当一个节点的所有前驱节点都已经计算出finish值才去计算这个节点的finish值。3.3 拓扑排序的状态更新逻辑实现时可以这样做统计每个任务的入度入度就是它的依赖任务数量把入度为0的任务加入队列这些任务没有依赖可以直接开始每次从队列取出一个任务u计算出finish[u]遍历u的所有后继任务v把finish[u]作为v的一个候选“前驱完成时间”更新maxDepFinish[v]v的入度减1代表v的一个依赖已经被处理当v的入度减到0时说明v的所有依赖任务都已经处理完毕此时maxDepFinish[v]已经统计了所有前驱完成时间中的最大值可以计算finish[v] maxDepFinish[v] duration[v]并把v加入队列。为什么入度减到0时计算是安全的因为只有当某个任务的所有前驱都被处理过它的maxDepFinish才可能被完整更新。如果入度还大于0说明还有前驱没有处理完此时计算出来的值只是一个中间值不完整。循环依赖的判断也顺带解决了如果图是DAG所有节点都能进入拓扑排序的队列最终处理节点数等于n。如果图有环环上的节点入度永远不会减到0它们永远不会进入队列最终处理节点数小于n。这时候输出-1即可。边界条件也需要考虑n1时只有唯一任务如果它依赖自身就是环否则输出它的耗时多个节点没有依赖它们可以并行不互相阻塞输入中的依赖顺序可能是乱序的不能默认任务ID就是输入顺序需要建立字符串ID到节点信息的映射耗时虽然最大只有100但路径长度可能累积到100000用Python的int完全没问题用C/Java时用int也够不需要long long。4. Python参考实现与易错点复盘4.1 完整代码下面是这道题的Python参考实现用最朴素的写法不依赖任何第三方库适合机试环境。import sys from collections import deque def solve(): data sys.stdin.read().strip().splitlines() if not data: return n int(data[0].strip()) duration {} adj {} indeg {} tasks [] # 第一遍读数据先记录所有任务ID for i in range(1, n 1): parts data[i].split() tid parts[0] dur int(parts[1]) tasks.append((tid, dur, parts[2] if len(parts) 2 else -)) duration[tid] dur adj[tid] [] indeg[tid] 0 # 第二遍解析依赖建图 for tid, dur, dep_str in tasks: if dep_str -: continue dep_list dep_str.split(,) for dep in dep_list: dep dep.strip() if not dep: continue # 依赖 dep - tid adj[dep].append(tid) indeg[tid] 1 # max_dep_finish[u] 表示 u 的所有前驱任务完成时间的最大值 max_dep_finish {tid: 0 for tid in duration} finish {} q deque([tid for tid in duration if indeg[tid] 0]) processed 0 while q: u q.popleft() processed 1 finish[u] max_dep_finish[u] duration[u] for v in adj[u]: max_dep_finish[v] max(max_dep_finish[v], finish[u]) indeg[v] - 1 if indeg[v] 0: q.append(v) if processed ! n: print(-1) else: print(max(finish.values())) if __name__ __main__: solve()4.2 关键行解读读数据部分用了两遍循环第一遍只读任务ID并初始化字典第二遍才解析依赖关系。这样做的目的是防止依赖列表里出现还没初始化的任务ID。如果图是合法的所有任务ID都应该出现在输入里但先初始化一遍更稳妥。max_dep_finish[tid] 0的初始值很关键。对于没有依赖的任务它直接等于0 duration[u]正好是“从0时刻开始做”。对于有依赖的任务它会在后续被前驱节点的finish值不断更新最终保留最大值。邻接表adj是由依赖节点指向后继节点的有向边。判断出度不是目的入度才是关键。indeg[u]表示任务u的依赖数量所以建图时每次遇到一个依赖就把indeg[tid]加1同时把tid加入adj[dep]的后继列表。队列循环里计算finish[u]的时机必须是在出队后立刻计算。不能提前也不能晚。提前的话max_dep_finish[u]可能还没更新完晚的话会影响后继节点的状态积累。4.3 上机环境里的输入输出陷阱我把这道题在本地跑通后又特意模拟了机试环境发现几个特别容易踩的输入输出坑。第一题目说依赖列表用逗号分隔但样例里的分隔符两边有没有空格这个不确定。稳妥做法是用split()把整行按空白拆成多个字段然后再对第三个字段按逗号分割。如果某个依赖项包含了空格就会拆错。但通常情况下任务ID和依赖列表之间是用空格分隔的所以parts[2]已经拿到了完整的依赖字符串。第二依赖字符串可能是空串吗如果某行写成了A 5 -parts[2]就是-这种好处理。但如果有人把无依赖写成A 5即整行只有两个字段len(parts) 2的判断就派上用场了。机试给的输入格式一般不会那么随意但自己处理时多做一层保护没有坏处。第三输出必须严格一行一个整数不要夹杂提示文字。比如在调试时打印print(ans, ans)上机提交前忘删整个答案就会错。这种问题在本地IDE里根本发现不了因为你看得到提示文字但判题系统只会比对数字输出。5. 真题题库使用建议与机考经验5.1 拿到一道题先做“考点映射”刷题库的时候我习惯把每道题在题号旁边标上考点标签。一个标签越具体越好不要只写“图论”要写“拓扑排序DP”。比如今天这道题我给的标签是数据建模任务依赖转DAG核心算法拓扑排序 最长路径DP工程细节字符串ID、逗号解析、-空依赖有了这种标签复习的时候就不需要重读整道题扫一眼标签就能回忆起每个考点的特征。更重要的是下次遇到类似的题目你会第一时间想到“哦这题很像任务依赖模型”而不是从零开始硬想。网上搜“华为OD机试真题题库”的时候经常会看到CSDN上的目录帖按C卷、D卷分类附带算法考点详解。这类内容很有参考价值但要注意它们的时效性。机考题目会更新输入输出格式也可能调整。以目录为索引以考点为主线才是正确用法。5.2 值得优先攻克的三个专题结合C卷的常见考点我个人最推荐优先攻克这三个专题拓扑排序与图论。这种题非常稳定代码模板不长却能把图的建模、队列的使用、状态更新全考一遍。而且它天然适合出成“依赖关系”“任务编排”“课程表”这类业务场景出题成本低区分度还高。动态规划。C卷里的DP题虽然不一定很难但状态设计比较灵活常见的是背包、最长递增子序列、区间DP、二维DP。DP题需要大量练习才会形成手感建议提前准备。字符串处理与模拟。ACM模式的机试非常考验字符串解析能力。很多看起来是“业务模拟”的题本质上是字符串切分、排序、哈希统计。这种题算法不难难在细心。这三个专题里拓扑排序和图论是性价比最高的。因为代码量适中思路清晰只要建图正确基本上不会出大问题适合在考场上拿分。5.3 复盘比刷新题重要我刷题有一个习惯就是错题至少做三遍。第一遍是独立做卡住了就看题解但看完以后必须自己把代码重新写出来。第二遍是隔一天再做不看题解只凭记忆和考点标签看看能不能独立写对。第三遍是隔一周再做重点检查自己是否真的理解了状态转移和边界处理而不是背代码。这个方法听起来慢但实际效率很高。因为机试题目是有套路的考点就那么多把一道综合题吃透比快速刷五道相似题更能形成长期记忆。尤其是今天这道“任务编排最早完成时间”它把拓扑排序、动态规划、字符串解析三个点串在一起只要真正吃透以后遇到类似图论题都会轻松很多。最后再分享一条机考经验考试时不要一上来就写代码。先用两到三分钟把输入输出和约束条件圈出来想清楚节点定义、状态定义、遍历顺序再动手。很多翻车不是因为算法不会而是因为题都没读透。双机位环境下你的每一次犹豫和切屏都会被放大与其坐到屏幕前手忙脚乱不如提前把流程练熟。说到底机试考的是稳定输出不是灵感爆发。