华为OD机试里有一道让我印象很深的模拟题题库里通常叫《精准核算检测》场景就是采样点排队的调度模拟。题干不长但把“多窗口排队 任务分配”两个核心考点都塞进去了采样点开了N个窗口每个窗口检测一位居民的耗时不一样M个居民陆陆续续到达系统要自动分配窗口最后输出每个人的等待时间、完成时间和整个采样工作的总耗时。如果你正在准备OD机试或者想系统练一下“优先队列 事件模拟”这一类题这篇文章值得看完。我把完整的Java实现、每一步的思考过程还有实际提交时容易踩的坑都整理出来了代码可以直接抄思路可以迁移到其他调度题。1. 先把“精准核算检测”翻译成算法模型1.1 题目规则到底长什么样我先按最常见的版本把题目规则固定下来后面所有代码都围绕这套规则展开采样点有N个检测窗口窗口编号从1到N。每个窗口完成一位居民采样的耗时不同用数组cost[i]表示单位是分钟。有M位居民第i位居民的到达时间用arrive[i]表示从采样点开始工作的0分钟算起。居民到达后由系统自动分配窗口。分配规则是选择当前“最快可服务”的窗口如果有多个窗口同时空闲或同时结束优先选编号最小的。需要输出每位居民被分配到的窗口编号、开始采样时间、完成采样时间、等待时间以及全部居民都完成采样后的总完成时间。这套规则翻译成算法语言就是有N个服务台每个服务台的处理速率固定M个任务按时间到达采用贪心策略——谁最快能接手任务就给谁。这里“最快能接手”包含两层含义如果存在已经空闲的窗口它们都能立刻接手选编号最小的如果所有窗口都忙就看谁手头的任务最早结束等它结束立刻接手。这本质上是一个最小化系统空闲时间的贪心调度也对应机试里最常见的版本。为什么题目值得单独拿出来写一篇因为它表面是生活场景实际考察的是对数据结构的敏感度。窗口数量N和居民数量M都可能上到十万级别如果没有选对数据结构暴力写法很容易超时。这一点在下一节具体展开。1.2 为什么优先队列是这道题的最优解很多第一次写这道题的人会选数组模拟用数组time[i]记录每个窗口当前排队任务的完成时间每来一个人就遍历所有窗口找time[i]最小的窗口再更新time[i] max(time[i], arrive) cost[i]。这个思路本身没错小数据量能跑但有两个问题。第一个问题是时间复杂度。假设窗口数量是10万居民人数也是10万每来一个人都要遍历一遍窗口总操作量是10^10量级在机试的时限下基本必挂。第二个问题是代码写起来啰嗦每次找最小值都要处理“多个相同最小值的窗口选哪个编号最小”这种细节稍有疏忽就出错。优先队列Java里的PriorityQueue天然就是干这个的它内部用堆维护最小值取最小值和插入值都是O(log N)级别的操作把整体复杂度降到O(M log M M log N)窗口数量再大也扛得住。而且只要在比较器里把“结束时间相同按编号升序”写进去“编号最小优先”这个规则也自动满足了。我自己的体会是这类排队模拟题只要看到“多个窗口”“多个服务台”“选择最早结束”这些关键词第一反应就应该是优先队列而不是用一个普通数组反复遍历求最小。2. Java实现之前三个设计决策必须想清楚2.1 数据结构居民对象数组 窗口优先队列代码里我会用两个核心数据结构居民列表ListPersonPerson包含编号id和到达时间arrive。按到达时间排序这样处理顺序和现实中的排队顺序一致。窗口优先队列PriorityQueuelong[]数组里存两个值窗口编号id和该窗口“下一次可开始服务的时间”也就是该窗口当前已经排到的所有任务都做完的时刻。队列按这个时间从小到大排列时间相同时按窗口编号排列。窗口队列里放long[]而不是自定义对象或包装类主要是为了减少内存和GC压力。机试环境虽然不像生产环境那么严苛但大批量数据下每来一个人就poll和offer一次用long[]确实比包装类更稳。比较器一定要用Long.compare不要用减法否则极端数据下可能溢出。这种错误在OJ上非常坑逻辑明明对结果却是WA排查半天才发现是减法溢出的问题。2.2 时间轴怎么推进按人到来的事件驱动而不是按分钟模拟我见过有人试图模拟真实时间线设置一个currentTime从0开始每分钟判断一次有没有人到达、有没有窗口结束。这种做法在小样例上能过可一旦时间范围达到几十万、几百万分钟直接循环就是灾难。正确做法是事件驱动把所有居民按到达时间排序依次处理每个人。当处理第i个人时队列里已经包含了所有窗口的最新状态“有人到达”这个事件触发一次窗口选择和执行。中间无人的空闲时间不需要关心因为那段时间系统状态不会变化直接跳到下一个人到达的时刻就行。事件驱动是模拟类题目的核心思想之后做很多复杂调度题都是这个套路状态不变化的时间段跳过不模拟。所以整体处理流程很简洁排序居民遍历每个居民从优先队列取最早可服务的窗口计算start和finish再把窗口放回队列。2.3 核心公式start max(arrive, freeAt)处理一位居民时从优先队列取出队首窗口记为w该窗口下一次可服务时间为freeAt。那么这位居民能开始采样的时间是start max(arrive, freeAt)含义很直白窗口早就空闲了居民一到就能开始窗口还在忙就得等窗口把手头的人送走也就是等到freeAt。接下来finish start cost[w] wait start - arrive这三行公式是整个算法的核心。后面的代码总共也就二十多行剩下的都是输入输出和数据结构搭建。想清楚这三行公式这道题就拿下了一半。3. 完整可提交的Java代码与逐段解析3.1 完整代码先放在这里import java.io.*; import java.util.*; public class Main { static class Person { int id; long arrive; Person(int id, long arrive) { this.id id; this.arrive arrive; } } public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st new StringTokenizer(br.readLine()); int N Integer.parseInt(st.nextToken()); long[] cost new long[N]; st new StringTokenizer(br.readLine()); for (int i 0; i N; i) { cost[i] Long.parseLong(st.nextToken()); } int M Integer.parseInt(br.readLine().trim()); ListPerson people new ArrayList(M); for (int i 0; i M; i) { st new StringTokenizer(br.readLine()); long arrive Long.parseLong(st.nextToken()); people.add(new Person(i, arrive)); } people.sort((a, b) - { if (a.arrive ! b.arrive) { return Long.compare(a.arrive, b.arrive); } return Integer.compare(a.id, b.id); }); PriorityQueuelong[] queue new PriorityQueue((x, y) - { if (x[1] ! y[1]) { return Long.compare(x[1], y[1]); } return Long.compare(x[0], y[0]); }); for (int i 0; i N; i) { queue.offer(new long[]{i, 0L}); } long totalFinish 0; StringBuilder sb new StringBuilder(); for (Person p : people) { long[] window queue.poll(); int windowId (int) window[0]; long freeAt window[1]; long start Math.max(p.arrive, freeAt); long finish start cost[windowId]; long wait start - p.arrive; totalFinish Math.max(totalFinish, finish); sb.append(居民).append(p.id) .append( - 窗口).append(windowId 1) .append(开始).append(start) .append(完成).append(finish) .append(等待).append(wait) .append(\n); queue.offer(new long[]{windowId, finish}); } sb.append(总完成时间).append(totalFinish); System.out.print(sb); } }这段代码可以直接提交到常见OJ的Java环境。类的命名是Main符合机试默认要求没有多余依赖只用JDK自带的集合和IO类。3.2 核心调度循环逐行拆解for循环里的代码是整个题目的心脏我一行一行说。long[] window queue.poll()取出当前所有窗口中“下一次可服务时间”最小的窗口。注意这里不区分窗口是否空闲空闲窗口的可服务时间就是上一次任务完成时间一定小于等于当前居民到达时间所以它也能被正常取出。long start Math.max(p.arrive, freeAt)开始时间是到达时间和窗口可服务时间的较大值。这一步同时处理了“窗口空闲”和“窗口忙碌”两种情况不需要额外写if分支。long finish start cost[windowId]完成时间等于开始时间加上该窗口服务一位居民的耗时。因为题目设定窗口效率不同同样的居民在不同的窗口完成时间可能差别很大这也是“精准分配”的意义所在。long wait start - p.arrive等待时间。由于start是max的结果wait一定非负不需要额外判断。queue.offer(new long[]{windowId, finish})把该窗口的新可服务时间放回队列。这一步非常关键很多新手容易漏漏了之后一个窗口只能服务一位居民后面的居民全部扎堆到其他窗口结果完全错乱。3.3 输入输出和性能细节这里提几个机试实战中的小细节。第一用BufferedReader加StringTokenizer代替Scanner数据量大的时候Scanner慢得明显虽然这题的输入规模不一定很大但养成好习惯对后续做题有好处。第二cost和arrive都用long存储因为累加后的完成时间可能超过int范围用int存导致溢出也是常见WA原因。第三输出用StringBuilder攒起来最后一次性输出而不是边处理边println避免大量IO调用拖慢速度。代码里窗口编号在内部统一从0开始输出的时候加1变成“窗口1”“窗口2”这样既方便数组索引又符合题目给用户看的编号习惯。4. 亲手推演一遍样例走查与结果验证4.1 标准样例的手工推演我们用一个具体输入来验证代码。假设输入3 6 4 8 5 0 5 10 15 20含义是3个窗口窗口1每人耗时6分钟窗口2每人耗时4分钟窗口3每人耗时8分钟5位居民分别在0、5、10、15、20分钟到达。手工推演过程如下表处理顺序居民到达时间选中窗口(原可服务时间)开始时间完成时间处理后各窗口可服务时间1居民00窗口1(0)06窗口1:6, 窗口2:0, 窗口3:02居民15窗口2(0)59窗口1:6, 窗口2:9, 窗口3:03居民210窗口3(0)1018窗口1:6, 窗口2:9, 窗口3:184居民315窗口1(6)1521窗口1:21, 窗口2:9, 窗口3:185居民420窗口2(9)2024窗口1:21, 窗口2:24, 窗口3:18程序输出的结果就是居民0 - 窗口1开始0完成6等待0 居民1 - 窗口2开始5完成9等待0 居民2 - 窗口3开始10完成18等待0 居民3 - 窗口1开始15完成21等待0 居民4 - 窗口2开始20完成24等待0 总完成时间24注意居民3在15分钟到达此时窗口1的可服务时间是6分钟已经空闲了9分钟所以优先选到它居民4在20分钟到达窗口1的可服务时间变成了21分钟还没空闲这时窗口2的可服务时间是9分钟所以被分到窗口2。每一步选中的都是“最早能接手”的窗口系统没有产生无谓的空闲等待。4.2 边界场景推演所有居民同时到达再看一种更极端的输入所有居民在同一时刻到达。假设2个窗口窗口1每人耗时5分钟窗口2每人耗时3分钟5位居民全部在0分钟到达。2 5 3 5 0 0 0 0 0处理过程居民0到窗口1开始0完成5。居民1到窗口2开始0完成3。居民2到达时窗口2可服务时间3分钟已经空闲窗口1可服务时间5分钟。不断言直接看队列top窗口2的3分钟更小所以居民2到窗口2开始3完成6。居民3到达时窗口1可服务时间5分钟窗口2可服务时间6分钟选择窗口1开始5完成10。居民4到达时窗口2可服务时间6分钟窗口1可服务时间10分钟选择窗口2开始6完成9。最终总完成时间是10分钟。可以看到快的窗口会被优先反复使用但慢窗口也在分承担负载这就是贪心调度的效果。如果全部塞给最快窗口慢窗口一直闲着反而可能让总时间变长所以“最快可服务”而不是“最快处理速度”才是这里的关键。5. 高频坑位与排查技巧实录5.1 最容易翻车的五个位置我在实际练习和帮朋友review代码的过程中发现这几个坑出现频率极高整理成一张表坑位典型表现解决办法比较器用减法极端大数下溢出答案WA用Long.compare居民没按到达时间排序分配结果错乱先按arrive排序同时到达没按编号二次排序同输入不同输出稳定性差排序加id比较poll之后忘了offer窗口只服务一个人更新后必须offer回去Scanner读入大输入数据量大时TLE换BufferedReader第一个坑最隐蔽。很多人写优先级队列比较器时习惯性写(int)(a[1] - b[1])在数据范围较小时没问题但一旦时间累加到很大int直接溢出排序结果完全错误。这类错误很难通过小样例发现只有大数据量压测才会暴露。我的建议是只要涉及时间计算一律用long比较器一律用Long.compare。第二个坑通常是没理解“处理顺序必须和到达时间一致”这个隐含条件。居民先来先分配这是现实逻辑也是题目隐含要求。不排序直接按输入顺序处理结果基本必错。第三个坑和第二个连在一起。如果两个居民同时到达谁先谁后机试一般要求稳定顺序那就按编号从小到大。实现时在排序比较器里把id作为第二关键字就行。5.2 排错技巧把每一步的状态打印出来如果你提交后是WA又不知道哪里错我的建议是别坐在屏幕前空想先加打印。把每个居民分配到的窗口、开始时间、完成时间和当前队列里的所有窗口状态都打出来然后拿样例手工推演一遍逐行对比。绝大多数情况下差异会集中在两类位置一类是队列里状态没更新另一类是排序规则不对。打印现场这个习惯我认为比任何调试工具都实用。因为模拟题本身就是“状态随时间推进”的过程人眼盯着代码看很难发现逻辑漏洞但一旦把每一步状态列成表格问题往往一眼就能看出。我刷类似题目时遇到WA基本都会用这个办法屡试不爽。5.3 关于“窗口编号从0还是1”的细节内部编号从0开始还是从1开始看似不起眼实际是很多低级WA的来源。我的习惯是内部一律从0开始存储和计算只有最终输出时才加1。这样数组下标、优先队列里的窗口id、输出编号三者各司其职不容易混。如果题目输入本身是把窗口编号当成1到N使用的也不建议直接改内部结构。比如把cost数组下标0空着不用窗口1对应cost[1]这样虽然减少了输出时的转换但所有遍历和初始化逻辑都要注意边界反而容易错。统一内部0偏移输出加1是最稳的做法。6. 这一类“排队调度”题还能怎么变6.1 换皮不换核银行叫号、服务器负载均衡这道题换个业务场景就是银行柜台叫号N个柜台每个柜台的业务办理速率不同客户到达时间给定要求输出每个客户的等待时间和总营业时间。再换一个场景就是服务器负载均衡N台服务器每台处理请求的耗时不同请求按时间到达负载器选择最快空闲的服务器转发请求。本质上都是“多服务窗口 任务到达 贪心选择最快可服务窗口”的模型。所以我的建议是不要只背这道题的代码把“事件驱动 优先队列维护服务窗口状态”这个组合记熟。机试里的模拟题很多但核心模型其实就那几类排队调度是最高频的一类。只要把这个模型的代码框架理解透遇到换皮题直接套只需要改输入输出和具体的耗时公式。6.2 常见变体和改造方法这道题常见的变体有不少我列几个典型的以及对应的改造点每个居民自带采样耗时而不是由窗口决定。这种情况把finish start cost[windowId]改成finish start p.serveTime就行其余逻辑完全不用动。窗口空闲时按编号最小优先而不是按“最快可服务”优先。这种情况仅靠一个优先队列不够需要额外用一个TreeSet维护当前空闲窗口编号每处理一个居民前先把队列里所有可服务时间小于等于到达时间的窗口转入空闲集合再从集合取最小编号。代码会多十几行但思路仍然是事件驱动。要求输出平均等待时间或最大等待时间。在循环里累加wait结束后除以M或取max即可。居民有预约时间不能提前开始。把start max(arrive, freeAt)改成start max(arrive, freeAt, reserveTime)就行。需要分两个阶段比如先登记再采样。那就跑两次调度第一阶段的完成时间作为第二阶段的到达时间或者用两个优先队列做两段事件流。这些变体都不难关键还是先把基础版本完全吃透。基础版的代码结构足够清晰改动起来就很轻松。最后分享一个我自己刷这类题的习惯写完代码先不急着提交拿一个样例手工跑一遍把每个窗口的可服务时间写在纸上再对照代码输出的每一步。只要有一处对不上基本就是比较器或者状态更新的问题。优先队列的题逻辑本身不复杂最容易翻车的是细节一次把所有细节想全比反复提交试错效率高得多。这道“精准核算检测”题目表面是排队内核是调度把它的解题模型练熟后面再遇到类似机试题你会觉得特别顺手。
