华为非 AI 方向机考 10·23:按序分苹果与带抢占的机器调度模拟
- 轮次
- 笔试
- 时间
- 2026-10
- 来源
- 牛客网
《面试题目》
第 1 题:按序分苹果(150 分)
- 有 n 个苹果排成一排、重量各不相同,要按站位顺序发给 k 个小朋友。规则:每人至少领一个、苹果不能剩下;苹果必须保持左右次序,只能切成 k 段连续的子段,第 1 段给最前面的小朋友,依次往后。求「所有分法里最大那一份的重量」能够压到的最小值。
- 样例:苹果重量按序为 4、1、5、2(共 4 只),发给 3 个小朋友,输出 5——对应切法 [4,1]、[5]、[2],三份分别是 5、5、2,最重的一份压到 5;另外两种切法 [4]、[1]、[5,2] 最重是 7,[4]、[1,5]、[2] 最重是 6。
第 2 题:机器调度模拟(150 分)
- 有 n 项任务在一台机器上跑,每项任务带编号 id、优先等级 p、抵达时刻 r、所需时长 d。机器任一时刻至多跑一项;一旦空闲就从等候队列挑一项开跑;任务正在跑时若有新任务抵达,只有新来者的 p 严格大于正在跑的这项,才允许抢占——被抢占的任务把剩余时间留下来放回队列;挑下一项按「p 从大到小、r 从早到晚、读入先后从先到后」三层比较;被抢占后放回队列时 p、r 与读入次序都保持原值;结束与抵达同一时刻时,必须先处理结束、再收进该时刻抵达的任务。输出任务编号按结束先后的顺序。
- 样例:4 项任务 (7,2,0,8)、(9,5,3,2)、(4,5,3,4)、(8,1,6,3),输出结束顺序 9 4 7 8。
《参考解析》
第 1 题:二分答案 + 贪心判定。 设「最重一份」的上限为 X,问题变成「能否切成不超过 k 段、每段重量都 ≤ X」。X 有单调性:X 可行则更大的 X 一定可行,因此可以二分。下界取最重的一只苹果(单独成段也至少要装下它),上界取总重量(只切一段)。判定函数从左往右贪心装段:遇到某只苹果本身就超过 X 直接失败;当前段再加一只就会超限时,就在这只之前切一刀、从它重新累加;扫完后统计段数是否 ≤ k。正确性靠「能多装就多装」:提前切开只会浪费当前段的剩余容量,而苹果顺序固定、后面的段数不会因此减少,所以贪心得到的段数就是该上限下的最少段数。正数重量下「段数 ≤ k」与「恰好切成 k 段」的最优值相同。复杂度 O(n log Σw)。实现上两个坑:用 64 位存总重,以及二分时用 low + (high - low) / 2 防止溢出。
第 2 题:事件驱动模拟 + 优先队列。 不要按时间单位逐步推进,只在「有新任务抵达」和「当前任务跑完」两类事件上推进时钟。数据结构:一个按抵达时刻排序的任务表,一个优先队列(比较器:p 降序 → r 升序 → 读入下标升序)存等待中的任务,一个变量存正在跑的任务及其剩余时间。每个事件时刻按固定顺序处理:① 把正在跑的任务的剩余时间推进到当前时刻,若剩余为 0 就记入结束序列;② 把当前时刻抵达的任务全部入堆;③ 若堆顶的 p 严格大于正在跑的 p,则抢占——把正在跑的任务(连同剩余时间、原 p/r/下标)放回堆,从堆顶取出新任务开跑;④ 若机器空闲,就反复取堆顶,时长为 0 的任务当场结束并继续取,直到取到正时长或堆空。关键点有三个:结束要先于抵达处理(否则同一时刻的先后会错)、抢占只比较优先级且必须严格大于(相等不抢占)、被抢占任务的 r 与读入次序不能被改成抢占时刻。每次抵达至多引发一次抢占,所以总进出堆次数是 O(n),整体 O(n log n)。
两道题共同的套路。 都能归到「先建模、再选标准工具」:第一题是「最大化最小值/最小化最大值」的典型二分答案,判定函数写成贪心;第二题是「带优先级与抢占的调度」,直接用堆做事件模拟,难点全在规则细节(同一时刻的处理次序、抢占条件、被抢占任务的状态保持)。机考里这类题的失分点很少在算法想不到,而在边界:取整、溢出、等号、并列时的次序。写完先用题面样例手推一遍,再补三组自造数据——最小规模、全部同优先级、多个任务同一时刻抵达——基本能覆盖大部分坑。