华为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四、测试用例测试用例11、输入35E,S,W,N0,1,3,62、输出9,93、说明E0 到达东西向红灯 - 3 进入 - 4 离开S1 到达南北向绿灯 - 1 进入 - 2 离开W3 到达东西向绿灯 - 3 进入 - 4 离开N6 到达南北向红灯 - 8 进入 - 9 离开总耗时 9 - 0 9最后离开时间 9测试用例21、输入23E,E,S1,3,42、输出5,63、说明E11 到达等待到 2 - 3 离开E23 到达前车正好在 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){ScannerscannernewScanner(System.in);intRInteger.parseInt(scanner.nextLine().trim());intGInteger.parseInt(scanner.nextLine().trim());String[]directionTokensscanner.nextLine().trim().split(\\s*,\\s*);String[]timeTokensscanner.nextLine().trim().split(\\s*,\\s*);intndirectionTokens.length;char[]directionsnewchar[n];int[]arrivalsnewint[n];for(inti0;in;i){directions[i]directionTokens[i].charAt(0);arrivals[i]Integer.parseInt(timeTokens[i]);}int[]resultsolve(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[]laneFreeTimenewint[4];intfirstArrivalarrivals[0];intlastLeaveTimefirstArrival;for(inti0;idirections.length;i){chardirdirections[i];intlanegetLaneIndex(dir);/* * 当前车辆想进入路口必须同时满足 * * 1. 自己已经到达 * 2. 同车道的前一辆车已经完全离开。 * * 因此取二者最大值。 */intearliestStartMath.max(arrivals[i],laneFreeTime[lane]);/* * earliestStart 只是车辆最早可以尝试进入的时刻。 * * 如果此时为绿灯可以直接走 * 如果此时为红灯则直接计算下一次绿灯开始时刻。 * * 不需要一秒一秒进行模拟。 */intactualStartgetNextGreenTime(earliestStart,dir,R,G);/* * 车辆通过路口需要 1 秒。 * * 例如车辆在 t3 时进入 * 则在 t4 时完全离开。 * * 下一辆同向车辆从 t4 开始可以再次判断信号灯。 */intleaveTimeactualStart1;laneFreeTime[lane]leaveTime;lastLeaveTimeMath.max(lastLeaveTime,leaveTime);}/* * 第一项 * 从第一辆车到达到最后一辆车离开的总耗时。 * * 第二项 * 最后一辆车完全离开的绝对时间。 */returnnewint[]{lastLeaveTime-firstArrival,lastLeaveTime};}/** * 返回从 time 开始本方向第一次可以进入路口的绿灯时刻。 */privatestaticintgetNextGreenTime(inttime,chardir,intR,intG){intcycleRG;intphasetime%cycle;if(dirE||dirW){/* * 东西向 * * [0, R) 红灯 * [R, R G) 绿灯 */if(phaseR){// 当前还在红灯阶段跳到本周期绿灯开始。returntime(R-phase);}// 当前已经是绿灯。returntime;}else{/* * 南北向恰好相反 * * [0, R) 绿灯 * [R, R G) 红灯 */if(phaseR){// 当前就是绿灯。returntime;}/* * 当前处于红灯 * 需要等到本周期结束也就是下一周期开始。 */returntime(cycle-phase);}}/** * 将四个方向映射到四条独立车道。 */privatestaticintgetLaneIndex(chardir){switch(dir){caseE:return0;caseW:return1;caseS:return2;caseN:return3;default:thrownewIllegalArgumentException(非法方向: dir);}}}七、效果展示1、输入42E,E,E0,1,22、输出11,113、说明东西向0~4 红4~6 绿6~10 红10~12 绿车辆E14 - 5E25 - 6E36 时已经变红只能等到 10 - 11输出11,11下一篇华为OD机试 - 简易内存池 - 逻辑分析Java 新系统 200分本专栏收录于《华为OD机试JAVA真题》。刷的越多抽中的概率越大私信哪吒备注华为OD加入华为OD刷题交流群每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景发现新题目随时更新全天CSDN在线答疑。