20260729-路口等待时间（N0056）- 算法机考高频题型 · 华为OD / 队列题解 | AlgoMooc

N0056. 20260729-路口等待时间

中等

通过率 78% · 提交 9 · 通过 7

200分华为OD队列模拟数学

改编自算法机考高频题型 · 200分 / 华为OD类型 · 难度：中等

十字路口的红绿灯分为东西向（E/W）和南北向（S/N）两组，两组状态始终相反。东西向红灯亮 R 秒，然后绿灯亮 G 秒，不断循环；南北向则相反——绿灯亮 R 秒，然后红灯亮 G 秒。刚开始时（0秒）东西方向是红灯，南北方向是绿灯。红绿灯切换无过渡期，红灯结束时绿灯立即开始，无需额外等待。车辆到达路口时，遇到绿灯直接走，通过路口需要 1 秒，如遇到红灯停下来等。E/W/S/N 四个方向各有一条独立车道，各自排队，互不干扰，而同向后车必须等前车走完才能走。求从第一辆车到达路口，到最后一辆车完全离开，共同花费多少秒，和最后一辆离开的时间是第几秒。

这类题属于算法机考高频题型中「200分 / 华为OD」方向的高频题型，通常考察对「200分 / 华为OD」的建模能力与边界条件处理。掌握本题的解题思路后，可举一反三应对同类真题方向，稳步提升机考通过率。

输入描述

整数 R：表示东西向红灯持续秒数（对应南北向绿灯时长）。
整数 G：表示东西向绿灯持续秒数（对应南北向红灯时长）。
字符数组：用大写字母表示车辆的来向列表，E=东向西，W=西向东，S=南向北，N=北向南。
整形数组：表示各车辆的到达时间。

输出描述

一维数组，包含第一辆车到达路口到最后一辆车完全离开的总耗时，以及最后一辆车离开的时间。补充说明：保证车辆的来向数量和到达时刻数量相等，且到达时刻按非递减顺序排列。取值范围：

1 ≤ R, G ≤ 60
到达时刻 ≤ 100
车辆数量 ≤ 100

示例

示例 1

输入示例

3
5
E,S,W,N
0,1,3,6

输出示例

9,9

说明：

周期 C = 8 秒。E/W 方向红灯条件：t % 8 < 3，S/N 方向红灯条件：t % 8 ≥ 3 所有车辆都在同个 C 周期内：

E 车 0 秒到达：0 < R 红灯，等 3 秒至 t = 3 开始通行，t = 4 离开（通行需 1 秒）
S 车 1 秒到达：直接绿灯通过，t = 1 开始，t = 2 离开
W 车 3 秒到达：R = 3，第 3 秒已是绿灯，t = 3 开始，t = 4 离开
N 车 6 秒到达：6 ≥ 3 红灯，需等 2 秒至下一周期 t = 8 开始通行，t = 9 离开最早到达=0 秒，最晚离开=9 秒，总时间=9−0=9 秒，最后一秒=9

示例 2

输入示例

2
3
E,E,S
1,3,4

输出示例

5,6

说明：

周期 C = 5 秒。E/W 方向红灯条件：t % 5 < 2 ，S/N 方向红灯条件：t % 5 ≥ 2 所有车辆都在同个 C 周期内：

E1 车 1 秒到达：1 < 2 红灯，等 1 秒至 t = 2 开始通行，t = 3 离开（通行需 1 秒）
E2 车 3 秒到达：3 ≥ 2 为绿灯；E1 已在 t = 3 离开，无需等待，E2 在 t = 3 开始，t = 4 离开
S 车 4 秒到达：4 ≥ 2 红灯，等 1 秒至下一周期 t = 5 开始，t = 6 离开最早到达=1 秒，最晚离开=6 秒，总时间=6−1=5 秒，最后一秒=6

时间限制 1000 ms · 内存限制 256 MB

本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。

问小欧 · 图解算法年卡¥99 开通 →

字号13Ctrl+/ 注释 · Ctrl+↵ 提交

from typing import List

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# @param R int 东西向红灯持续秒数
# @param G int 东西向绿灯持续秒数
# @param directions List[str] 车辆的来向列表
# @param arrivals List[int] 各车辆的到达时间
# @return List[int] 包含总耗时和最后一辆车离开时间的数组
class Solution:
    def trafficLight(self, R: int, G: int, directions: List[str], arrivals: List[int]) -> List[int]:
        pass

# 以下内容为LeetCode核心代码模式转为ACM模式所需代码
# 请在algomooc oj上直接使用，在实际考试中无需编写
if __name__ == "__main__":
    R = int(input().strip())
    G = int(input().strip())
    directions = input().strip().split(",")
    arrivals = list(map(int, input().strip().split(",")))
    sol = Solution()
    ans = sol.trafficLight(R, G, directions, arrivals)
    print(",".join(map(str, ans)))

写完代码点「提交」，将对全部测试用例判题。

输入描述

输出描述

示例

我的提交