华为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 数据结构：居民对象数组 + 窗口优先队列

代码里我会用两个核心数据结构：

• 居民列表：List<Person>，Person包含编号id和到达时间arrive。按到达时间排序，这样处理顺序和现实中的排队顺序一致。
• 窗口优先队列：PriorityQueue<long[]>，数组里存两个值：窗口编号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()); List<Person> 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); }); PriorityQueue<long[]> 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分钟到达。手工推演过程如下表：

程序输出的结果就是：

居民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代码的过程中，发现这几个坑出现频率极高，整理成一张表：

第一个坑最隐蔽。很多人写优先级队列比较器时习惯性写(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)就行。
• 需要分两个阶段，比如先登记再采样。那就跑两次调度，第一阶段的完成时间作为第二阶段的到达时间，或者用两个优先队列做两段事件流。

这些变体都不难，关键还是先把基础版本完全吃透。基础版的代码结构足够清晰，改动起来就很轻松。

最后分享一个我自己刷这类题的习惯：写完代码先不急着提交，拿一个样例手工跑一遍，把每个窗口的可服务时间写在纸上，再对照代码输出的每一步。只要有一处对不上，基本就是比较器或者状态更新的问题。优先队列的题逻辑本身不复杂，最容易翻车的是细节，一次把所有细节想全，比反复提交试错效率高得多。这道“精准核算检测”题目，表面是排队，内核是调度，把它的解题模型练熟，后面再遇到类似机试题，你会觉得特别顺手。