华为OD机考C卷里“停车场收入统计”这道题乍一看是个生活场景题实际上是一道很典型的业务模拟题核心考察时间处理、排序、优先队列和贪心模拟。用Java写起来框架不难但坑很多。不少同学和我一样第一眼看到“收入统计”就以为把每辆车的停车费简单相加结果在车位容量、计费取整、车辆拒单这些地方反复踩雷。这篇就把这道题的常见题面、解题思路、完整Java实现和机考实战注意点一次说清楚适合正在准备OD机考、尤其是冲刺C卷前两题的朋友参考。1. 题目到底在问什么从标题反推常见题面1.1 一个可以落地的题面版本先说清楚一个前提这个标题没有附带完整题面所以下面的题设是我基于历年OD机考同类型题目做的最常见还原也是大多数“停车场收入统计”变体的通用框架。实际考试时你拿到的可能在这个基础上改条件但核心逻辑不会跑偏。常见题面长这样某停车场有 M 个车位每个车位收费标准不同单位是元/小时。一天内有 N 辆车进场每辆车有入场时间和出场时间。车辆到达时如果刚好有空闲车位就停入其中一个车位如果所有车位都占用则该车辆直接离场不计费。停车费用按实际停放时间计算不足 1 小时按 1 小时计算。统计停车场一天的总收入。输入格式通常这样组织第一行停车位数量 M第二行M 个整数表示每个车位每小时的收费单价第三行车辆数量 N接下来 N 行每行两个时间入场时间和出场时间格式为 HH:mm输出格式就是一个数字总收入。举个例子2 5 8 3 08:10 09:10 08:30 10:00 09:00 11:00这个例子里有两个车位单价分别是 5 和 8。三辆车的收入最后算出来是 18后面我会演示完整的计算过程。1.2 这道题为什么值得认真复盘OD机考的题目有一个很明显的特点喜欢把算法题包装成业务场景。“停车场收入统计”只是其中一种类似的还有仓库租赁计费、机房算力分配、影厅排片统计。这种包装本质上不改变算法内核但很考验你从场景里抽取出数据模型的能力。这道题融合了三个高频考点时间处理把 HH:mm 转成可计算的数值处理跨小时、跨天。区间调度车辆占用车位本质上是时间段占用资源和会议室安排是同构问题。优先队列维护空闲车位和正在被占用的车位时堆是最合适的结构。会做这道题意味着你基本掌握了OD机考里很大一类“业务模拟题”的通用解法。这也是我强烈建议考前把它吃透的原因。2. 解题思路拆解先别碰键盘把逻辑盘清楚2.1 时间统一到分钟为什么必须这么做拿到时间字符串第一件事永远是统一单位。这是一个看似基础但极其重要的习惯。08:10 和 09:10 两个时间肉眼一看就是 1 小时但程序里字符串比较只能判断先后不能做差值计算。如果直接对字符串截断小时做减法又会遇到跨小时的问题比如 08:45 到 09:05看起来小时数相减是 9 - 8 1 小时实际上只有 20 分钟。最稳妥的做法是全部转成分钟static int toMinute(String hhmm) { String[] t hhmm.split(:); return Integer.parseInt(t[0]) * 60 Integer.parseInt(t[1]); }08:10 转成 490 分钟09:10 转成 550 分钟差值 60 分钟干净利落。后面所有排序、比较、计费都基于这个分钟数不再碰原始字符串。这里还要提一个容易漏掉的边界如果出场时间小于入场时间说明这辆车跨天了比如 23:30 进、01:20 出。这种情况需要在出场时间上加 24 * 60 1440 分钟再参与计算。不少考过这套题的人反馈跨天处理是隐藏扣分点题面不会明说但测试数据里很可能出现。2.2 两个优先队列是解题的关键结构模拟停车过程最核心的数据结构是两个堆。第一个堆维护当前空闲车位的单价用最大堆也就是每次取出的都是单价最高的空闲车位。这是模拟策略的一部分系统自动分配时优先给车辆安排收费贵的车位这样总收入更高。第二个堆维护当前正在被占用的车位存的是离开时间和对应车位的单价用最小堆按离开时间从小到大排列。这样每次有新车辆到达时能快速知道哪些车已经走了、释放了哪些车位。为什么不用数组遍历去维护这些状态因为每辆车到达时都要检查所有车位是否空闲、检查所有正在停的车是否已经离开最坏情况是 O(N*M) 的时间复杂度。机考数据量大时很容易超时。用两个堆之后每次释放和分配都是 O(log M)整体复杂度是 O(N log M)稳得多。这里有一个非常容易想歪的点有人会觉得用一个布尔数组标记每个车位是否被占再用一个数组存每辆车的离开时间每次遍历一遍就行。对小数据量确实能跑通但一旦 M 和 N 到几千甚至上万效率差距就出来了。机考判题不仅看结果还要看运行时间所以优先队列不是炫技是必要选择。2.3 按时间扫描的事件模拟模型整个主流程可以理解成一个收银台排队问题。车辆按入场时间排序后从头到尾处理。处理每一辆车时第一步不是急着找空位而是先看看当前有哪些车已经走了。怎么判断看第二个堆的堆顶如果堆顶的离开时间不晚于当前车辆的入场时间说明这辆车已经离场它占用的车位释放把单价加回空闲堆。这个步骤反复执行直到堆顶的离开时间晚于当前车辆的入场时间。第二步才是尝试分配车位。从空闲堆里取出单价最高的车位如果没有空闲车位当前车辆直接拒单进入下一个车辆的循环。如果分配成功把该车位的单价乘上停车时长累加到总收入同时把当前车辆的离开时间和所用车位单价放入占用堆。这个模型的关键点在于释放车位的时机是“当前车辆到达时”而不是“时间每走一分钟就检查一次”。后者实现复杂且没有必要前者只需要在车辆到达的事件点上做释放判断即可逻辑上完全覆盖了时间段冲突。2.4 计费向上取整一个容易翻车的细节停车时长不足 1 小时按 1 小时计费所以必须向上取整。分钟差值算出来之后除以 60 要向上取整。最容易写错的是下面这种int hours (leave - arrival) / 60;这是向下取整59 分钟直接变成 0 小时收入变成 0明显不符合题意。正确的写法是long hours (leave - arrival 59) / 60;比如差值是 59 分钟(59 59) / 60 118 / 60 1符合不足 1 小时按 1 小时。差值是 60 分钟(60 59) / 60 119 / 60 1也正确。差值是 120 分钟(120 59) / 60 179 / 60 2正确。注意不要用浮点数去做除法再向上取整比如 Math.ceil((leave - arrival) / 60.0)这样容易在精度边界上出问题而且要多写一次类型转换。整数运算加 59 再整除是最干净的方案。还有一个坑是整数溢出。如果单价和时长都是十万级别相乘就是一千万再累加多个车辆int 很容易装不下。所以收入累加用 long车位的单价也用 long 存从一开始就避免这个问题。3. Java代码实现完整可运行的版本3.1 数据结构与输入解析先定义车辆信息类。机考现场写代码类定义越精简越好不要搞继承、接口那些花活够用就行。static class Car { int arrival; // 入场时间的分钟表示 int leave; // 出场时间的分钟表示 long hours; // 停车时长向上取整后的小时数 Car(int arrival, int leave, long hours) { this.arrival arrival; this.leave leave; this.hours hours; } }输入解析我用 Scanner机考数据量不极端时完全够用。如果遇到特别大的输入可以换 BufferedReader但可读性会差一些。我习惯先用 Scanner 把逻辑写对确认无误后再考虑性能优化。解析时要特别注意行尾空格问题。用 nextLine() 读进来之后务必调 trim() 再去 split不然最后一个字段后面多一个空格会导致解析错误这个错在线判题里非常常见而且报错信息很隐晦。3.2 核心模拟流程主流程代码我按步骤拆开写方便对照上面的思路看。import java.util.*; public class Main { static class Car { int arrival; int leave; long hours; Car(int arrival, int leave, long hours) { this.arrival arrival; this.leave leave; this.hours hours; } } public static void main(String[] args) { Scanner sc new Scanner(System.in); int m Integer.parseInt(sc.nextLine().trim()); String[] feeParts sc.nextLine().trim().split( ); long[] fees new long[m]; for (int i 0; i m; i) { fees[i] Long.parseLong(feeParts[i]); } int n Integer.parseInt(sc.nextLine().trim()); ListCar cars new ArrayList(); for (int i 0; i n; i) { String[] parts sc.nextLine().trim().split( ); int arrival toMinute(parts[0]); int leave toMinute(parts[1]); if (leave arrival) { leave 24 * 60; // 跨天处理 } long hours (long) ((leave - arrival 59) / 60); cars.add(new Car(arrival, leave, hours)); } // 按入场时间排序同时保持相同入场时间的输入顺序 cars.sort(Comparator.comparingInt(c - c.arrival)); // 空闲车位单价最大堆 PriorityQueueLong free new PriorityQueue(Collections.reverseOrder()); for (long fee : fees) { free.offer(fee); } // 占用中的车位离开时间 - 单价最小堆 PriorityQueuelong[] occupied new PriorityQueue(Comparator.comparingLong(a - a[0])); long total 0; for (Car car : cars) { // 步骤一释放所有已经离开的车位 while (!occupied.isEmpty() occupied.peek()[0] car.arrival) { long[] top occupied.poll(); free.offer(top[1]); } // 步骤二尝试分配车位 if (!free.isEmpty()) { long fee free.poll(); total fee * car.hours; occupied.offer(new long[]{car.leave, fee}); } } System.out.println(total); } static int toMinute(String hhmm) { String[] t hhmm.split(:); return Integer.parseInt(t[0]) * 60 Integer.parseInt(t[1]); } }这段代码的核心就两个 while 循环加一个 if。while 循环负责释放车位if 负责分配车位清晰对应前面梳理的事件模型。3.3 测试用例与预期输出用前面给的例子测一下2 5 8 3 08:10 09:10 08:30 10:00 09:00 11:00手动推演一遍车 108:10 到达09:10 离开时长 1 小时。此时两个车位都空闲系统选择单价 8 的车位收入 8占用堆里存 (550, 8)。车 208:30 到达10:00 离开时长 2 小时不足 2 小时按 2 小时90分钟向上取整是 2。释放阶段占用堆堆顶是 550 分钟晚于 510不释放。此时只剩单价 5 的车位分配收入 5*210占用堆存 (600, 5)。车 309:00 到达11:00 离开时长 2 小时。释放阶段占用堆堆顶是 550也就是车 1 在 09:10 离开但车 3 到达是 09:0009:10 晚于 09:00不释放。车 2 离开时间是 600也就是 10:00也不释放。空闲堆为空车 3 被拒单。总收入 8 10 18。再测一个边界用例重点验证同一时刻离开与到达的处理1 10 2 08:00 09:00 09:00 10:00车 1 在 09:00 离开车 2 在 09:00 到达。由于释放条件用了occupied.peek()[0] car.arrival所以车 2 到达时能先释放车 1 的车位再正常分配。总收入 10 10 20。如果你写的是车 2 会被误拒输出只有 10对一半。很多机考模拟题的隐藏条件就是这种“同进同出谁先谁后”的问题题面不会明确写但测试数据里会有。我的处理原则是在业务逻辑上说得通的就按说得通的来车辆离开和到达同时发生时车位应当释放后立刻复用。3.4 两个细节优化稳定排序和跨天处理我在代码里用Comparator.comparingInt(c - c.arrival)排序。Java 的 sort 对对象数组和 ArrayList 是稳定排序相同入场时间的车辆会保持输入顺序。这样当多辆车同时到达而车位不足时先输入的车优先分配不会出现随机拒单的情况。虽然大多数题目不强调这个但稳定排序能减少不确定因素。跨天处理在代码里体现在if (leave arrival) { leave 24 * 60; }这个判断放在时间转换之后、时长计算之前。如果题目明确说所有车辆都在同一天内进出加不加都不影响。但一旦遇到跨天数据这个判断就是救命的。要注意的是这种处理方式只适用于“出场时间字符串小于入场时间字符串就表示跨天”的约定。如果题面的时间字段里带了日期那就不能这么简单处理需要把日期也解析进来。好在OD机考里不带日期的场景更常见。4. 机考实战经验从易错点到应试节奏4.1 高频易错点速查表我把这类题踩过的坑整理成一个速查表考前过一遍很有用。易错点后果正确做法时间不转分钟直接操作字符串计算差值出错、跨小时判断困难统一转成分钟所有计算基于分钟数出场时间小于入场时间不做处理时长变成负数计费异常出场时间加 1440 分钟处理跨天向上取整写成直接整除不足 1 小时被算成 0 小时收入漏算差值加 59 再整除 60收入累加用 int数据量大时整数溢出用 long 类型存储和计算释放车位的时机不对车位占用状态错乱拒掉本可分配的车车辆到达时先 while 释放所有已离场车位空闲车位用最小堆找单价最高每次取到的是最低价收入变低单价用最大堆Collections.reverseOrder()字符串解析不去除行尾空格split 结果含空串解析报错读入后先 trim() 再处理这些坑单个看都是小问题但组合在一起很容易让你在调试上浪费大量时间。机考总共三个小时前两题的时间非常宝贵一题卡半小时就会影响后面的节奏。4.2 双机位机考环境下的应试细节双机位是OD机考的硬件要求一个摄像头从正面拍摄考生面部和屏幕另一个从侧面后方拍摄环境用于防作弊。这个设置对做题本身没有直接影响但它决定了一个关键约束你无法像平时练习那样随意翻阅本地资料、切换IDE窗口。有几条经验值得提前准备第一提交代码用的在线编辑器通常没有智能提示代码补全能力很弱。平时从 IDE 复制粘贴习惯了到考场会很不适应。考前一周我建议直接用系统的记事本或者在线编辑器练习写代码把常用模板背下来比如 Scanner 解析模板、PriorityQueue 初始化、sort 的 lambda 写法。这些代码量不大背下来比现场想更快。第二输入输出必须用标准输入输出。有些同学在本地练习时习惯读文件比如从 txt 读数据然后输出到控制台。考场平台只认 System.in 和 System.out文件读写会直接判 0 分。这个属于低级错误但每年都有人犯。第三机考过程中会有屏幕录制所以不要试图开额外的浏览器窗口查资料。与其想着作弊不如老实刷题。我个人的体会是双机位环境反而让人更专注因为没有手机和社交软件的干扰思维连续性比在家刷题还好。第四代码风格不要花哨。判题系统只关心输入输出是否符合预期不需要你写多优雅的多态设计。一个 Main 类、几个静态方法、私有静态内部类就是最合适的结构。越简单出错的可能性越低。4.3 从停车场收入扩展出去业务模拟题的通法总结这道题最大的价值在于它代表了一整类“业务模拟题”。我复盘了这个题之后总结出一套通用处理流程后面再做类似的题基本都能套。读题阶段先抽取四个要素实体是什么状态有哪些时间如何表达计费规则是什么。停车场这道题里实体是车位和车辆状态是空闲和占用时间是入场和出场计费规则是按小时和向上取整。建模阶段想清楚三个问题时间线怎么扫描事件点有哪些状态切换用什么数据结构。停车场的答案是入场时间作为扫描顺序事件点是每辆车的到达状态切换用两个堆。实现阶段按照“读入所有数据 - 按事件排序 - 处理每个事件 - 累加结果”的固定节奏推进不要边写边想。先把主流程的空架子搭出来再把细节填进去。这个方法我后来套到过仓库租赁统计、机房资源计费、会议室排期这些题目上发现核心代码几乎不用大改改的只是实体字段和计费公式。所以在考场上一看到“XX统计”这种题第一反应不是慌而是快速判断能不能套事件模拟模板。能套基本就稳了。最后分享一个我自己调试的小心得。写完代码之后不要只跑题目给的样例一定要自己构造三个测试场景第一个是全满场景所有车辆都停得进去第二个是拒单场景必须拒绝至少一辆车第三个是边界场景包含整点进出和不足一小时计费。这三个场景覆盖了大多数隐藏问题。我第一次写停车场这道题时就是靠自定义的边界用例发现了释放条件写错的问题在考场上省下了二十分钟的排查时间。