华为OD机试 - 路口等待时间（Python/JS/C/C++ 新系统 200分）

华为OD机试 新系统 统一考试题库清单（持续收录中）以及考点说明（Python/JS/C/C++）。

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新。

一、题目描述

十字路口的红绿灯分为东西向（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

五、解题思路

1. 红绿灯按周期循环
   • 一个完整周期为 R + G 秒。对于任意时刻 t，通过 t % (R + G) 判断当前处于周期中的哪个阶段：
   • E/W：前 R 秒红灯，后 G 秒绿灯。
   • S/N：前 R 秒绿灯，后 G 秒红灯。
2. 记录四条车道的最早可用时间
   • E、W、S、N 四个方向互不影响，因此用长度为 4 的数组 laneFreeTime，分别记录每个方向前一辆车完全离开的时间。
3. 依次处理每辆车
   • 当前车辆最早能准备通过的时间为：
   • max(车辆到达时间, 同方向前车离开时间)
   • 如果此时是绿灯，立即进入；如果是红灯，则根据红绿灯周期直接计算下一次绿灯开始时间，不用逐秒等待。
4. 计算离开时间
   • 车辆通过路口需要 1 秒，因此：
   • 离开时间 = 实际进入时间 + 1
   • 更新该方向车道的可用时间，同时维护所有车辆中的最晚离开时间。
5. 计算最终答案
   • 总耗时 = 最后一辆车离开时间 - 第一辆车到达时间
   • 输出：总耗时,最后离开时间

六、Python算法源码

defnext_green_time(time,direction,r,g):cycle=r+g phase=time%cycleifdirectionin('E','W'):""" 东西向： [0, R) 红灯 [R, R + G) 绿灯 """ifphase<r:# 当前在红灯，直接跳到本周期绿灯开始时刻。returntime+(r-phase)returntimeelse:""" 南北向与东西向相反： [0, R) 绿灯 [R, R + G) 红灯 """ifphase<r:returntime# 红灯期间直接等待到下一个周期开始。returntime+(cycle-phase)defsolve(r,g,directions,arrivals):lane_index={'E':0,'W':1,'S':2,'N':3}# 四个方向是四条独立车道，# 分别保存同车道前一辆车的离开时间。lane_free_time=[0]*4first_arrival=arrivals[0]last_leave_time=first_arrivalfordirection,arrivalinzip(directions,arrivals):lane=lane_index[direction]""" 当前车辆最早可以尝试进入的时间， 必须同时满足： 1. 当前车已经到达； 2. 同车道前车已经完全离开。 """earliest_start=max(arrival,lane_free_time[lane])# 根据红绿灯周期直接寻找下一次绿灯，# 而不是逐秒等待。actual_start=next_green_time(earliest_start,direction,r,g)# 通过路口需要固定 1 秒。leave_time=actual_start+1lane_free_time[lane]=leave_time last_leave_time=max(last_leave_time,leave_time)return(last_leave_time-first_arrival,last_leave_time)r=int(input().strip())g=int(input().strip())directions=[x.strip()forxininput().split(',')]arrivals=[int(x.strip())forxininput().split(',')]elapsed,last_leave=solve(r,g,directions,arrivals)print(f"{elapsed},{last_leave}")

七、JavaScript算法源码

constfs=require('fs');constlines=fs.readFileSync(0,'utf8').trim().split(/\r?\n/);constR=Number(lines[0].trim());constG=Number(lines[1].trim());constdirections=lines[2].split(',').map(s=>s.trim());constarrivals=lines[3].split(',').map(s=>Number(s.trim()));functionnextGreenTime(time,direction,R,G){constcycle=R+G;constphase=time%cycle;if(direction==='E'||direction==='W'){/* * 东西向： * [0, R) 红灯 * [R, R + G) 绿灯 * * 当前如果在红灯区间， * 直接跳到当前周期的绿灯起点。 */returnphase<R?time+(R-phase):time;}/* * 南北向： * [0, R) 绿灯 * [R, R + G) 红灯 * * 如果处于红灯，则需要等到下一个周期。 */returnphase<R?time:time+(cycle-phase);}functionsolve(R,G,directions,arrivals){constlaneIndex={E:0,W:1,S:2,N:3};/* * 四个方向是四条独立车道。 * 保存每条车道上一辆车完全离开的时间。 */constlaneFreeTime=[0,0,0,0];constfirstArrival=arrivals[0];letlastLeaveTime=firstArrival;for(leti=0;i<directions.length;i++){constdirection=directions[i];constlane=laneIndex[direction];/* * 同车道后车必须等待前车完全离开， * 因此车辆最早能尝试进入的时间是： * * max(自身到达时间, 前车离开时间) */constearliestStart=Math.max(arrivals[i],laneFreeTime[lane]);constactualStart=nextGreenTime(earliestStart,direction,R,G);// 通过路口需要固定 1 秒。constleaveTime=actualStart+1;laneFreeTime[lane]=leaveTime;lastLeaveTime=Math.max(lastLeaveTime,leaveTime);}return[lastLeaveTime-firstArrival,lastLeaveTime];}const[elapsed,lastLeave]=solve(R,G,directions,arrivals);console.log(`${elapsed},${lastLeave}`);

八、C算法源码

#include<stdio.h>#include<stdlib.h>#include<string.h>#include<ctype.h>intget_lane_index(chardir){if(dir=='E')return0;if(dir=='W')return1;if(dir=='S')return2;return3;// N}intnext_green_time(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;}/* * 南北向： * * [0, R) 绿灯 * [R, R + G) 红灯 */if(phase<R){returntime;}// 红灯期间直接等待到下一周期。returntime+(cycle-phase);}intmain(void){intR,G;chardirection_line[1024];chartime_line[2048];chardirections[100];intarrivals[100];intn=0;intm=0;scanf("%d",&R);scanf("%d",&G);/* * 清理第二个整数后这一行剩余字符， * 这样可以兼容常见的不同换行格式。 */intch;while((ch=getchar())!='\n'&&ch!=EOF){}fgets(direction_line,sizeof(direction_line),stdin);fgets(time_line,sizeof(time_line),stdin);/* * 解析方向数组，例如： * * E,S,W,N */char*token=strtok(direction_line,",");while(token!=NULL&&n<100){while(isspace((unsignedchar)*token)){token++;}directions[n++]=*token;token=strtok(NULL,",");}/* * 解析车辆到达时间数组，例如： * * 0,1,3,6 */token=strtok(time_line,",");while(token!=NULL&&m<100){while(isspace((unsignedchar)*token)){token++;}arrivals[m++]=atoi(token);token=strtok(NULL,",");}/* * 四条独立车道分别记录： * 同车道前一辆车完全离开的时间。 */intlane_free_time[4]={0,0,0,0};intfirst_arrival=arrivals[0];intlast_leave_time=first_arrival;for(inti=0;i<n;i++){intlane=get_lane_index(directions[i]);/* * 当前车必须： * * 1. 自己已经到达； * 2. 同车道前车已经离开。 * * 所以取二者最大值。 */intearliest_start=arrivals[i]>lane_free_time[lane]?arrivals[i]:lane_free_time[lane];intactual_start=next_green_time(earliest_start,directions[i],R,G);// 车辆进入后经过 1 秒离开。intleave_time=actual_start+1;lane_free_time[lane]=leave_time;if(leave_time>last_leave_time){last_leave_time=leave_time;}}printf("%d,%d\n",last_leave_time-first_arrival,last_leave_time);return0;}

九、C++算法源码

#include<iostream>#include<sstream>#include<string>#include<vector>#include<array>#include<algorithm>#include<limits>usingnamespacestd;intgetLaneIndex(chardir){if(dir=='E')return0;if(dir=='W')return1;if(dir=='S')return2;return3;// N}intnextGreenTime(inttime,chardir,intR,intG){intcycle=R+G;intphase=time%cycle;if(dir=='E'||dir=='W'){/* * 东西向： * * [0, R) 红灯 * [R, R+G) 绿灯 * * 如果处于红灯， * 直接跳到当前周期绿灯开始时刻。 */returnphase<R?time+(R-phase):time;}/* * 南北向与东西向相反： * * [0, R) 绿灯 * [R, R+G) 红灯 */returnphase<R?time:time+(cycle-phase);}intmain(){intR,G;cin>>R>>G;/* * 清理整数输入所在行剩余内容， * 避免后面的 getline 读到空行。 */cin.ignore(numeric_limits<streamsize>::max(),'\n');string directionLine;string timeLine;getline(cin,directionLine);getline(cin,timeLine);vector<char>directions;vector<int>arrivals;string token;/* * 解析车辆方向数组。 */stringstreamds(directionLine);while(getline(ds,token,',')){size_t pos=token.find_first_not_of(" \t\r\n");directions.push_back(token[pos]);}/* * 解析到达时间数组。 */stringstreamts(timeLine);while(getline(ts,token,',')){arrivals.push_back(stoi(token));}/* * E/W/S/N 是四条独立车道。 * * laneFreeTime 保存同车道 * 前一辆车辆完全离开的时间。 */array<int,4>laneFreeTime{0,0,0,0};intfirstArrival=arrivals[0];intlastLeaveTime=firstArrival;for(size_t i=0;i<directions.size();++i){intlane=getLaneIndex(directions[i]);/* * 当前车辆至少要等到： * * 1. 自己到达； * 2. 同车道前车离开。 */intearliestStart=max(arrivals[i],laneFreeTime[lane]);/* * 再根据灯的周期， * 直接寻找可以进入的绿灯时刻。 */intactualStart=nextGreenTime(earliestStart,directions[i],R,G);// 车辆通过路口需要 1 秒。intleaveTime=actualStart+1;laneFreeTime[lane]=leaveTime;lastLeaveTime=max(lastLeaveTime,leaveTime);}cout<<lastLeaveTime-firstArrival<<','<<lastLeaveTime<<'\n';return0;}

🏆下一篇：华为OD机试真题 - 简易内存池（Python/JS/C/C++ 新系统 200分）

🏆本文收录于，华为OD机试真题（Python/JS/C/C++）

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新。