华为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四、测试用例测试用例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更新该方向车道的可用时间同时维护所有车辆中的最晚离开时间。计算最终答案总耗时 最后一辆车离开时间 - 第一辆车到达时间输出总耗时,最后离开时间六、Python算法源码defnext_green_time(time,direction,r,g):cyclerg phasetime%cycleifdirectionin(E,W): 东西向 [0, R) 红灯 [R, R G) 绿灯 ifphaser:# 当前在红灯直接跳到本周期绿灯开始时刻。returntime(r-phase)returntimeelse: 南北向与东西向相反 [0, R) 绿灯 [R, R G) 红灯 ifphaser:returntime# 红灯期间直接等待到下一个周期开始。returntime(cycle-phase)defsolve(r,g,directions,arrivals):lane_index{E:0,W:1,S:2,N:3}# 四个方向是四条独立车道# 分别保存同车道前一辆车的离开时间。lane_free_time[0]*4first_arrivalarrivals[0]last_leave_timefirst_arrivalfordirection,arrivalinzip(directions,arrivals):lanelane_index[direction] 当前车辆最早可以尝试进入的时间 必须同时满足 1. 当前车已经到达 2. 同车道前车已经完全离开。 earliest_startmax(arrival,lane_free_time[lane])# 根据红绿灯周期直接寻找下一次绿灯# 而不是逐秒等待。actual_startnext_green_time(earliest_start,direction,r,g)# 通过路口需要固定 1 秒。leave_timeactual_start1lane_free_time[lane]leave_time last_leave_timemax(last_leave_time,leave_time)return(last_leave_time-first_arrival,last_leave_time)rint(input().strip())gint(input().strip())directions[x.strip()forxininput().split(,)]arrivals[int(x.strip())forxininput().split(,)]elapsed,last_leavesolve(r,g,directions,arrivals)print(f{elapsed},{last_leave})七、JavaScript算法源码constfsrequire(fs);constlinesfs.readFileSync(0,utf8).trim().split(/\r?\n/);constRNumber(lines[0].trim());constGNumber(lines[1].trim());constdirectionslines[2].split(,).map(ss.trim());constarrivalslines[3].split(,).map(sNumber(s.trim()));functionnextGreenTime(time,direction,R,G){constcycleRG;constphasetime%cycle;if(directionE||directionW){/* * 东西向 * [0, R) 红灯 * [R, R G) 绿灯 * * 当前如果在红灯区间 * 直接跳到当前周期的绿灯起点。 */returnphaseR?time(R-phase):time;}/* * 南北向 * [0, R) 绿灯 * [R, R G) 红灯 * * 如果处于红灯则需要等到下一个周期。 */returnphaseR?time:time(cycle-phase);}functionsolve(R,G,directions,arrivals){constlaneIndex{E:0,W:1,S:2,N:3};/* * 四个方向是四条独立车道。 * 保存每条车道上一辆车完全离开的时间。 */constlaneFreeTime[0,0,0,0];constfirstArrivalarrivals[0];letlastLeaveTimefirstArrival;for(leti0;idirections.length;i){constdirectiondirections[i];constlanelaneIndex[direction];/* * 同车道后车必须等待前车完全离开 * 因此车辆最早能尝试进入的时间是 * * max(自身到达时间, 前车离开时间) */constearliestStartMath.max(arrivals[i],laneFreeTime[lane]);constactualStartnextGreenTime(earliestStart,direction,R,G);// 通过路口需要固定 1 秒。constleaveTimeactualStart1;laneFreeTime[lane]leaveTime;lastLeaveTimeMath.max(lastLeaveTime,leaveTime);}return[lastLeaveTime-firstArrival,lastLeaveTime];}const[elapsed,lastLeave]solve(R,G,directions,arrivals);console.log(${elapsed},${lastLeave});八、C算法源码#includestdio.h#includestdlib.h#includestring.h#includectype.hintget_lane_index(chardir){if(dirE)return0;if(dirW)return1;if(dirS)return2;return3;// N}intnext_green_time(inttime,chardir,intR,intG){intcycleRG;intphasetime%cycle;if(dirE||dirW){/* * 东西向 * * [0, R) 红灯 * [R, R G) 绿灯 */if(phaseR){// 直接跳到本周期绿灯起点。returntime(R-phase);}returntime;}/* * 南北向 * * [0, R) 绿灯 * [R, R G) 红灯 */if(phaseR){returntime;}// 红灯期间直接等待到下一周期。returntime(cycle-phase);}intmain(void){intR,G;chardirection_line[1024];chartime_line[2048];chardirections[100];intarrivals[100];intn0;intm0;scanf(%d,R);scanf(%d,G);/* * 清理第二个整数后这一行剩余字符 * 这样可以兼容常见的不同换行格式。 */intch;while((chgetchar())!\nch!EOF){}fgets(direction_line,sizeof(direction_line),stdin);fgets(time_line,sizeof(time_line),stdin);/* * 解析方向数组例如 * * E,S,W,N */char*tokenstrtok(direction_line,,);while(token!NULLn100){while(isspace((unsignedchar)*token)){token;}directions[n]*token;tokenstrtok(NULL,,);}/* * 解析车辆到达时间数组例如 * * 0,1,3,6 */tokenstrtok(time_line,,);while(token!NULLm100){while(isspace((unsignedchar)*token)){token;}arrivals[m]atoi(token);tokenstrtok(NULL,,);}/* * 四条独立车道分别记录 * 同车道前一辆车完全离开的时间。 */intlane_free_time[4]{0,0,0,0};intfirst_arrivalarrivals[0];intlast_leave_timefirst_arrival;for(inti0;in;i){intlaneget_lane_index(directions[i]);/* * 当前车必须 * * 1. 自己已经到达 * 2. 同车道前车已经离开。 * * 所以取二者最大值。 */intearliest_startarrivals[i]lane_free_time[lane]?arrivals[i]:lane_free_time[lane];intactual_startnext_green_time(earliest_start,directions[i],R,G);// 车辆进入后经过 1 秒离开。intleave_timeactual_start1;lane_free_time[lane]leave_time;if(leave_timelast_leave_time){last_leave_timeleave_time;}}printf(%d,%d\n,last_leave_time-first_arrival,last_leave_time);return0;}九、C算法源码#includeiostream#includesstream#includestring#includevector#includearray#includealgorithm#includelimitsusingnamespacestd;intgetLaneIndex(chardir){if(dirE)return0;if(dirW)return1;if(dirS)return2;return3;// N}intnextGreenTime(inttime,chardir,intR,intG){intcycleRG;intphasetime%cycle;if(dirE||dirW){/* * 东西向 * * [0, R) 红灯 * [R, RG) 绿灯 * * 如果处于红灯 * 直接跳到当前周期绿灯开始时刻。 */returnphaseR?time(R-phase):time;}/* * 南北向与东西向相反 * * [0, R) 绿灯 * [R, RG) 红灯 */returnphaseR?time:time(cycle-phase);}intmain(){intR,G;cinRG;/* * 清理整数输入所在行剩余内容 * 避免后面的 getline 读到空行。 */cin.ignore(numeric_limitsstreamsize::max(),\n);string directionLine;string timeLine;getline(cin,directionLine);getline(cin,timeLine);vectorchardirections;vectorintarrivals;string token;/* * 解析车辆方向数组。 */stringstreamds(directionLine);while(getline(ds,token,,)){size_t postoken.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 保存同车道 * 前一辆车辆完全离开的时间。 */arrayint,4laneFreeTime{0,0,0,0};intfirstArrivalarrivals[0];intlastLeaveTimefirstArrival;for(size_t i0;idirections.size();i){intlanegetLaneIndex(directions[i]);/* * 当前车辆至少要等到 * * 1. 自己到达 * 2. 同车道前车离开。 */intearliestStartmax(arrivals[i],laneFreeTime[lane]);/* * 再根据灯的周期 * 直接寻找可以进入的绿灯时刻。 */intactualStartnextGreenTime(earliestStart,directions[i],R,G);// 车辆通过路口需要 1 秒。intleaveTimeactualStart1;laneFreeTime[lane]leaveTime;lastLeaveTimemax(lastLeaveTime,leaveTime);}coutlastLeaveTime-firstArrival,lastLeaveTime\n;return0;}下一篇华为OD机试真题 - 简易内存池Python/JS/C/C 新系统 200分本文收录于华为OD机试真题Python/JS/C/C刷的越多抽中的概率越大私信哪吒备注华为OD加入华为OD刷题交流群每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景发现新题目随时更新。