华为OD机试 - 路口等待时间（Java 新系统 200分）
华为OD机试 新系统 题库疯狂收录中，刷题点这里
专栏导读
本专栏收录于《华为OD机试（JAVA）真题》。
刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。
一、题目描述
十字路口的红绿灯分为东西向（E/W）和南北向（S/N）两组，两组状态始终相反。东西向红灯亮 R 秒，然后绿灯亮 G 秒，不断循环；
南北向则相反——绿灯亮 R 秒，然后红灯亮 G 秒。刚开始时（0 秒）东西方向是红灯，南北方向是绿灯。
红绿灯切换 0 无过渡期，红灯结束时绿灯立即开始，无需额外等待。
车辆到达路口时，遇到绿灯直接走，通过路口需要 1 秒，如遇到红灯停下来等。E/W/S/N 四个方向各有一条独立车道，各自排队，互不
干扰，而同向后车必须等前车走完才能走。
求从第一辆车到达路口，到最后一辆车完全离开，共同花费多少秒，和最后一辆离开的时间是第几秒。
二、输入描述
• 整数 R：表示东西向红灯持续秒数（对应南北向绿灯时长）。
• 整数 G：表示东西向绿灯持续秒数（对应南北向红灯时长）。
• 字符数组：用大写字母表示车辆的来向列表，E=东向西，W=西向东，S=南向北，N=北向南。
• 整形数组：表示各车辆的到达时间。
三、输出描述
一维数组，包含第一辆车到达路口到最后一辆车完全离开的总耗时，以及最后一辆车离开的时间。
补充说明：
保证车辆的来向数量和到达时刻数量相等，且到达时刻按非递减顺序排列。
取值范围：
• 1 ≤ R,G ≤ 60
• 到达时刻 ≤ 100
• 车辆数量 ≤ 100
四、测试用例
测试用例1：
1、输入
3
5
E,S,W,N
0,1,3,6
2、输出
9,9
3、说明
E：0 到达，东西向红灯 -> 3 进入 -> 4 离开
S：1 到达，南北向绿灯 -> 1 进入 -> 2 离开
W：3 到达，东西向绿灯 -> 3 进入 -> 4 离开
N：6 到达，南北向红灯 -> 8 进入 -> 9 离开
总耗时 = 9 - 0 = 9
最后离开时间 = 9
测试用例2：
1、输入
2
3
E,E,S
1,3,4
2、输出
5,6
3、说明
E1：1 到达，等待到 2 -> 3 离开
E2：3 到达，前车正好在 3 离开 -> 3 进入 -> 4 离开
S ：4 到达，此时南北向红灯 -> 5 进入 -> 6 离开
第一辆车在第 1 秒到达，因此：
总耗时 = 6 - 1 = 5
五、解题思路
- 红绿灯按周期循环
- 一个完整周期为 R + G 秒。对于任意时刻 t，通过 t % (R + G) 判断当前处于周期中的哪个阶段：
- E/W：前 R 秒红灯，后 G 秒绿灯。
- S/N：前 R 秒绿灯，后 G 秒红灯。
- 记录四条车道的最早可用时间
- E、W、S、N 四个方向互不影响，因此用长度为 4 的数组 laneFreeTime，分别记录每个方向前一辆车完全离开的时间。
- 依次处理每辆车
- 当前车辆最早能准备通过的时间为：
- max(车辆到达时间, 同方向前车离开时间)
- 如果此时是绿灯，立即进入；如果是红灯，则根据红绿灯周期直接计算下一次绿灯开始时间，不用逐秒等待。
- 计算离开时间
- 车辆通过路口需要 1 秒，因此：
- 离开时间 = 实际进入时间 + 1
- 更新该方向车道的可用时间，同时维护所有车辆中的最晚离开时间。
- 计算最终答案
- 总耗时 = 最后一辆车离开时间 - 第一辆车到达时间
- 输出：总耗时,最后离开时间
六、Java算法源码
publicclassOdTest{publicstaticvoidmain(String[]args){Scannerscanner=newScanner(System.in);intR=Integer.parseInt(scanner.nextLine().trim());intG=Integer.parseInt(scanner.nextLine().trim());String[]directionTokens=scanner.nextLine().trim().split("\\s*,\\s*");String[]timeTokens=scanner.nextLine().trim().split("\\s*,\\s*");intn=directionTokens.length;char[]directions=newchar[n];int[]arrivals=newint[n];for(inti=0;i<n;i++){directions[i]=directionTokens[i].charAt(0);arrivals[i]=Integer.parseInt(timeTokens[i]);}int[]result=solve(R,G,directions,arrivals);System.out.println(result[0]+","+result[1]);}privatestaticint[]solve(intR,intG,char[]directions,int[]arrivals){/* * E、W、S、N 四个方向是四条独立车道。 * * laneFreeTime[i] 表示对应车道中， * 前一辆车完全离开路口的时间。 * * 0 -> E * 1 -> W * 2 -> S * 3 -> N */int[]laneFreeTime=newint[4];intfirstArrival=arrivals[0];intlastLeaveTime=firstArrival;for(inti=0;i<directions.length;i++){chardir=directions[i];intlane=getLaneIndex(dir);/* * 当前车辆想进入路口，必须同时满足： * * 1. 自己已经到达； * 2. 同车道的前一辆车已经完全离开。 * * 因此取二者最大值。 */intearliestStart=Math.max(arrivals[i],laneFreeTime[lane]);/* * earliestStart 只是车辆最早可以尝试进入的时刻。 * * 如果此时为绿灯，可以直接走； * 如果此时为红灯，则直接计算下一次绿灯开始时刻。 * * 不需要一秒一秒进行模拟。 */intactualStart=getNextGreenTime(earliestStart,dir,R,G);/* * 车辆通过路口需要 1 秒。 * * 例如车辆在 t=3 时进入， * 则在 t=4 时完全离开。 * * 下一辆同向车辆从 t=4 开始可以再次判断信号灯。 */intleaveTime=actualStart+1;laneFreeTime[lane]=leaveTime;lastLeaveTime=Math.max(lastLeaveTime,leaveTime);}/* * 第一项： * 从第一辆车到达到最后一辆车离开的总耗时。 * * 第二项： * 最后一辆车完全离开的绝对时间。 */returnnewint[]{lastLeaveTime-firstArrival,lastLeaveTime};}/** * 返回从 time 开始，本方向第一次可以进入路口的绿灯时刻。 */privatestaticintgetNextGreenTime(inttime,chardir,intR,intG){intcycle=R+G;intphase=time%cycle;if(dir=='E'||dir=='W'){/* * 东西向： * * [0, R) 红灯 * [R, R + G) 绿灯 */if(phase<R){// 当前还在红灯阶段，跳到本周期绿灯开始。returntime+(R-phase);}// 当前已经是绿灯。returntime;}else{/* * 南北向恰好相反： * * [0, R) 绿灯 * [R, R + G) 红灯 */if(phase<R){// 当前就是绿灯。returntime;}/* * 当前处于红灯， * 需要等到本周期结束，也就是下一周期开始。 */returntime+(cycle-phase);}}/** * 将四个方向映射到四条独立车道。 */privatestaticintgetLaneIndex(chardir){switch(dir){case'E':return0;case'W':return1;case'S':return2;case'N':return3;default:thrownewIllegalArgumentException("非法方向: "+dir);}}}七、效果展示
1、输入
4
2
E,E,E
0,1,2
2、输出
11,11
3、说明
东西向：
0~4 红
4~6 绿
6~10 红
10~12 绿
车辆：
E1：4 -> 5
E2：5 -> 6
E3：6 时已经变红，只能等到 10 -> 11
输出：
11,11
🏆下一篇：华为OD机试 - 简易内存池 - 逻辑分析（Java 新系统 200分）
🏆本专栏收录于《华为OD机试（JAVA）真题》。
刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。