更新题目 环形 hub：无人机最小耗时
题目 amazon-drone-hub-ring · 修改（rev 5） · · 2026-10-27 00:33
body
@@ -1,196 +1,225 @@ +## TL;DR + +- 先问清 `transitionTime[i]` 指什么。截图样例只能把四种读法分成两组（「题目」里的表），本页按「离开 Hub i 的耗时」写【推断】。 +- 每办完一个请求，无人机停在已知的 hub 上，所以各段互相独立，总耗时等于每段最短耗时之和（「思路」第 1 步）。 +- 在耗时非负的前提下，每段只比较一路顺时针和一路逆时针两种走法（「思路」第 2 步）。 +- 用前缀和把每个方向的耗时变成 $O(1)$，总复杂度 $O(m + n)$（「思路」第 3 步、「复杂度」）。 +- 三个坑：连续访问同一个 hub 要跳过，Hub m 到 Hub 1 那一步要回绕，Java、C++ 的累加要用 64 位整数（「易错点」）。 + ## 题目 -Amazon 的无人机配送网络有 m 个 hub（站点），编号 1..m，首尾相连围成一个环，所以 Hub 1 和 Hub m 也相邻。无人机每一步只能移到左边或右边相邻的那个 hub。数组 `transitionTime` 的长度是 m，下标从 1 开始（1-based），它给出移动的耗时，题面原话是 "the travel time between Hub i and its neighbors is given by transitionTime[i]"。 - -`requestedHubs` 的长度是 n，是一串优先配送请求：无人机必须按给定的顺序，依次到这些 hub 取件或送达。无人机从 **Hub 1** 出发，要求的是办完全部请求所需的最小总移动耗时。题里的 hub 编号和数组下标都从 1 开始。 - -### 样例 - -题面截图里给出的样例是： - -- m = 3，n = 4 -- transitionTime = [3, 2, 1] -- requestedHubs = [1, 3, 3, 2] -- 无人机从 Hub 1 出发 - -截图到这里就截断了，期望输出、样例解释和数据范围都没有露出来。 - -样例里 3 连着出现了两次。【推断】这表示无人机在 Hub 3 连着办两件事（比如先送达、再取件），中间不用移动，这一段耗时为 0。帖子底下的回复里有人这样问过，楼主（发帖人）没有回答。 - -### transitionTime[i] 到底指什么 - -题面只说 Hub i 和它的邻居之间的耗时是 transitionTime[i]（下面简写成 t[i]），没有说清楚这个耗时算在哪一步、对应哪条边，所以有歧义。至少有四种自然的读法：两种把 t[i] 看成挂在 Hub i 这个点上的耗时，分别是离开 Hub i 时花的「离开耗时」和走进 Hub i 时花的「到达耗时」；另外两种把 t[i] 看成一条边的权重，也就是边权（edge weight），区别在于这条边是 Hub i 前面那一条还是后面那一条。下表里的「顺时针（clockwise）」指编号增大的方向，「逆时针（counter-clockwise）」指编号减小的方向。把样例代进去，四种读法算出的答案只分成两组（帖子回复里正好有人问答案「是 3 还是 4」，楼主没有回答）： - -| 读法 | 1→3 | 3→2 | 合计 | +m 个 hub（站点）编号 1..m，首尾相连围成一个环，Hub 1 和 Hub m 也相邻。无人机每一步移到左边或右边相邻的 hub。数组 `transitionTime` 长度为 m，下标从 1 开始，题面原话是 "the travel time between Hub i and its neighbors is given by transitionTime[i]"（下面把 `transitionTime[i]` 简写成 t[i]）。 + +`requestedHubs` 长度为 n，是一串配送请求，无人机必须按给定顺序依次到这些 hub。无人机从 **Hub 1** 出发，求办完全部请求的最小总移动耗时。 + +题面截图里的样例是 m = 3、`transitionTime = [3, 2, 1]`、`requestedHubs = [1, 3, 3, 2]`。截图在这里截断，期望输出、样例解释和数据范围都没有露出来。样例里 3 连着出现两次，【推断】意思是在 Hub 3 连着办两件事，这一段不用移动，耗时为 0。 + +### transitionTime[i] 有四种读法 + +题面只说 Hub i 和邻居之间的耗时是 t[i]，没说这个耗时算在哪一步。两种读法把 t[i] 挂在 Hub i 这个点上：离开 Hub i 时花 t[i]（离开耗时），或走进 Hub i 时花 t[i]（到达耗时）。另两种把 t[i] 当成一条边的权重（边权，edge weight），区别是这条边在 Hub i 的哪一侧。下面说的「顺时针（clockwise）」指编号增大的方向 1 → 2 → … → m → 1，「逆时针（counter-clockwise）」指编号减小的方向。 + +样例里 1 → 1 和 3 → 3 两段耗时都是 0，只剩 1 → 3 和 3 → 2 两段要算： + +| 读法 | 1 → 3 | 3 → 2 | 合计 | |---|---|---|---| -| 离开耗时（代码里叫 `leave`）：从 Hub i 走到任一邻居都花 t[i] | 3（逆时针，离开 1） | 1（逆时针，离开 3） | **4** | -| 边权（前一条，`edge_prev`）：t[i] 是 Hub i−1 与 Hub i 之间的边，t[1] 连 Hub m 和 Hub 1 | 3（3–1 那条边是 t[1]；顺时针 2+1 也是 3） | 1（2–3 那条边是 t[3]） | **4** | -| 到达耗时（`arrive`）：走进 Hub i 花 t[i] | 1（逆时针，走进 3） | 2（逆时针，走进 2） | **3** | -| 边权（后一条，`edge_next`）：t[i] 是 Hub i 与 Hub i+1 之间的边，t[m] 连 Hub m 和 Hub 1 | 1（3–1 那条边是 t[3]） | 2（2–3 那条边是 t[2]） | **3** | - -样例里另外两段 1→1 和 3→3 的起点和终点相同，四种读法下耗时都是 0。 - -所以，就算知道了样例输出，也只能排除一组读法：输出 4，剩下「离开耗时」和「边权（前一条）」；输出 3，剩下「到达耗时」和「边权（后一条）」。同一组里的两种读法在别的输入上会给出不同的答案。例如 t = [1, 10, 1, 1] 时，从 Hub 2 走到 Hub 1，离开耗时是 10，边权（前一条）是 3；从 Hub 1 走到 Hub 2，到达耗时是 10，边权（后一条）是 1。要最终确定是哪一种，还得靠题面全文，或者样例解释里给出的每一步耗时；截图没有露出这部分，题面到底有没有写清楚，未核实。 - -本页的代码把四种读法都实现了，用 `mode` 参数切换，默认按「离开耗时」算【推断】。支持离开耗时和支持边权的依据都列在下面；除了截图里那句题面原文，其余都是楼主们凭记忆的转述。 - -- **支持离开耗时的依据。** 题面把耗时挂在 Hub i 这个点上，而不是挂在某条边上（这一点到达耗时读法也符合）。一位 OA 通过的在职跳槽楼主补充说，transition time「记得是离开的cost」；他转引的一亩三分地论坛旧帖，描述里写的也是「各点出发去相邻点的cost」。 -- **支持边权的依据。** 另外几篇帖子的楼主用的都是「距离」一类的说法：「hub之间有distance」「给出每个hub和adjacent hub的距离」「告诉环上每两个点之间的间隔时长」。还有一位 OA 通过的楼主说这题像 LeetCode 1184 Distance Between Bus Stops 的变形（「不是完全一样」）。那道题给的是相邻两站之间的距离，所以【推断】照 LeetCode 1184 的设定看，更像边权读法。不过离开耗时读法的解法同样是前缀和（prefix sum，见「思路」）加上每段在两个方向里取较小值，所以这个类比其实分辨不出是哪一种读法。【推断】这些「距离」的说法，也可能只是楼主把题面那句 between Hub i and its neighbors 顺口说成了距离。 - -### 不同帖子的说法和变体 - -- 有一篇帖子写的是无人机顺时针送快递、按路线送完后求总时间，同一篇还说题目告诉了环上每两个点之间的间隔时长。那篇开头说自己做了「一些模糊处理」，所以【推断】「顺时针」可能是模糊或简化过的说法；另一篇写的就是顺时针、逆时针两个方向都能走，求最短耗时。如果真遇到只许顺时针飞的版本，把每一段「两个方向取较小值」那一步去掉即可。 -- 一亩三分地网站自己用 AI 整理过这道题（下称站方 AI 版本，内容未经原帖证实）。这些版本有的写成 0-based（下标从零开始）、从 hub 0 或从 requestedHubs[0] 出发，还附了 10^5–2×10^5、10^9 量级的数据范围和示例。其中一份示例写的输出是 7，解释却算出 9，所以别拿这些示例来对答案。截图里写明了是从 Hub 1 出发。 +| 离开耗时：从 Hub i 走到任一邻居花 t[i] | 3（逆时针，离开 Hub 1） | 1（逆时针，离开 Hub 3） | 4 | +| 边权（前一条）：t[i] 是 Hub i−1 和 Hub i 之间的边，t[1] 连 Hub m 和 Hub 1 | 3（3–1 这条边是 t[1]，顺时针 2 + 1 也是 3） | 1（2–3 这条边是 t[3]） | 4 | +| 到达耗时：走进 Hub i 花 t[i] | 1（逆时针，走进 Hub 3） | 2（逆时针，走进 Hub 2） | 3 | +| 边权（后一条）：t[i] 是 Hub i 和 Hub i+1 之间的边，t[m] 连 Hub m 和 Hub 1 | 1（3–1 这条边是 t[3]） | 2（2–3 这条边是 t[2]） | 3 | + +截图那篇帖子底下正好有人问样例答案「是 3 还是 4」，楼主没有回答。就算知道了输出，也只能排除一组：输出 4 剩下离开耗时和边权（前一条），输出 3 剩下到达耗时和边权（后一条）。同一组里的两种读法在别的输入上会分开，例如 t = [1, 10, 1, 1] 时，从 Hub 2 走到 Hub 1，离开耗时是 10，边权（前一条）只要 3。要定下来，得看样例解释里每一步的耗时。 + +本页默认按离开耗时写【推断】。依据有两条：题面把耗时挂在 Hub i 这个点上，一位 OA 通过的楼主也说 transition time「是离开的 cost」，他转引的一亩三分地旧帖写的是「各点出发去相邻点的 cost」。另外几位楼主说的是「hub 之间有 distance」「相邻 hub 的距离」，听着像边权，但也可能只是把 between Hub i and its neighbors 顺口说成了距离。四种读法的解法相同，只差每个方向的求和区间，改法见「代码」后面的表。 + +> [!say] Before coding I'd like to confirm what transitionTime[i] means: the cost of leaving hub i, the cost of entering it, or the weight of the edge on one side of it. The sample output alone only narrows it down to two readings, so I'd check the per-step costs in the sample explanation. + +### 不同帖子的说法 + +- 有一篇写的是无人机「顺时针」送快递，那篇开头说自己做了模糊处理。别的帖子都写两个方向都能飞、求最短耗时。只许顺时针的版本见 Follow-up。 +- 一亩三分地站方用 AI 整理过这道题（下称站方 AI 版本，未经原帖证实）。有的版本写成下标从 0 开始、从 `requestedHubs[0]` 出发，附了 $2 \times 10^5$ 个 hub、单个耗时 $10^9$ 量级的数据范围。其中一份示例写输出 7，解释却算出 9，别拿来对答案。截图写明从 Hub 1 出发，以截图为准。 ## 面经里怎么考的 -这道题是 Amazon SDE OA 里的编程题，排在第一题，限时 40 分钟。2026-04 底到 07 底做 OA 的人陆续碰到过它（帖子发在 2026-05 到 09）。在职跳槽的 SDE II 和应届生（new grad，NG）都考到过，应届生里既有加拿大的 NG，也有投 Amazon Leo 团队、职位名写作 SPL-SDE1 的应届生。一位 4 月底收到 OA 的加拿大 NG 楼主说一亩三分地上有原题，一位 7 月底做 OA 的 SDE II 楼主说在小红书上看到过原题。 - -### 整场 OA 的格式 - -整场 OA 100 分钟，共两题，这道占 40 分钟；第二题是 60 分钟的 AI 辅助调试题，见 [[q:amazon-oa-ai-debug]]。有的帖子说编程之后还有不限时的 Work Simulation 和 Work Style（[[q:amazon-oa-work-simulation]]）：前者是给工作场景里的几种回复或做法打分或排序的情景判断题，后者是工作风格问卷，都是选择题。 - -考试环境方面，一位投 AWS 的楼主说平台是 HackerRank；一位 5 月初收到 OA 的应届楼主说不需要出示带照片的证件（photo ID），也不用开摄像头。那张题面截图左上角的计时器显示还剩 39 min 35 sec。右边的代码编辑器看起来是 Python 模板【推断】：显示语言的 Language 栏被截掉了，只能从以 `def`、`if` 开头的行和 `#` 注释来判断。 - -### 楼主们怎么描述这道题 - -- 5 月中发帖的一位 SDE II 在职跳槽楼主（OA 通过）说，这题像 LeetCode 1184 的变形，但不完全一样：LeetCode 那道只算一次两点之间的距离，这题要把很多段的距离累加起来。他的做法是先用前缀和预处理，然后每一段取两个方向里较短的那个，再累加。 -- 一位投 AWS 的在职跳槽楼主（5 月做的 OA，通过）说题目很长，要花点时间才能读懂。题目给的是每个 hub 和相邻 hub 之间的距离，去每个目的地都有顺时针、逆时针两种走法，用前缀和就能求出来，数据范围（constraint）上没有什么特别要注意的。 -- 6 月发帖的一位在职跳槽楼主（通过）说，这道题一亩三分地上之前有人发过，并转引了那段描述：从各点出发去相邻点有一个 cost，路径上的点首尾相接，从尾部出发去头部的那一步有坑，要小心。他自己补充了两点：一是 transition time 记得是离开时的 cost；二是要认真读题，切记头尾相连。 - -### 卡在哪 - -- 5 月初做 OA 的一位应届楼主（投的是 Amazon Leo）最后得分 8/15，提到有一个 m = 2 的环形边界情况（edge case）没解决；后来照样收到了进入下一轮的通知（move forward）。 -- 6 月发帖的一位博士、在职跳槽的楼主说「测试都没过」（没有分题说明），这篇帖子标注的结果是 Fail（没通过）。他对题目的描述是 hub 之间有 distance。 -- 截图那篇帖子底下的回复问了三件事：样例答案是 3 还是 4；[1, 3, 3, 2] 是不是先飞到 3 送货、再在 3 取货；楼主的测试过没过。楼主都没有回。分歧就出在 transitionTime 的含义上（见上面「题目」一节）。 - -### 教训 - -【推断】OA 看起来不要求所有测试用例都通过：得分 8/15 的、第二题没修完的都进了下一轮（评分规则未核实）。另外，因为 transitionTime 的含义有歧义，动手写代码之前，先把样例按几种读法都算一遍；如果样例解释里给了每一步的耗时，就以它为准。然后把 m = 1、m = 2、Hub m → Hub 1、连续访问同一个 hub 这些边界情况都手算一遍。 +这是 Amazon SDE OA 编程部分的第一题，帖子发在 2026-05 到 09。在职跳槽的 SDE II 和应届生（new grad，NG）都考到过，应届生里有加拿大的 NG，也有投 Amazon Leo 团队、职位名写作 SPL-SDE1 的。一位 4 月底收到 OA 的加拿大 NG 楼主说一亩三分地上有原题，一位 7 月底做 OA 的 SDE II 楼主说在小红书上看到过原题。 + +编程部分共 100 分钟两题，这道题限时 40 分钟，第二题是 60 分钟的 AI 辅助调试题 [[q:amazon-oa-ai-debug]]。有的帖子说编程之后还有不限时的 Work Simulation 和 Work Style（[[q:amazon-oa-work-simulation]]），都是选择题。一位投 AWS 的楼主说平台是 HackerRank。一位 5 月初收到 OA 的应届楼主说不用出示带照片的证件（photo ID），也不用开摄像头。题面截图左上角的计时器显示还剩 39 min 35 sec，和 40 分钟的限时对得上。右边编辑器看着是 Python 模板【推断】，显示语言的那一栏被截掉了，只能从 `def` 开头的行和 `#` 注释判断。 + +说了做法的几位楼主都是先做前缀和，每段取顺时针、逆时针里较短的那个，再累加。一位 SDE II 楼主说这题像 LeetCode 1184 Distance Between Bus Stops 的变形，区别是 1184 只算一次两点距离，这题要把很多段累加起来。投 AWS 的那位楼主说题目很长，读懂要花点时间，数据范围（constraint）上没什么要特别注意的。转引旧帖的那位楼主提醒，从尾部去头部的那一步有坑，要切记头尾相连。 + +卡住的情况有这几种： + +- 一位投 Amazon Leo 的应届楼主得分 8/15，说有一个 m = 2 的环形边界情况没解决，OA 照样通过了。 +- 投 AWS 的那位楼主没全过测试，OA 也通过了。另一位应届楼主以为自己挂了，结果收到了 VO（virtual onsite，OA 之后的正式面试轮）。 +- 一位博士、在职跳槽的楼主说「测试都没过」（没分题说），OA 没通过。他对题目的描述是 hub 之间有 distance。 +- 截图那篇帖子底下的回复问了三件事：样例答案是 3 还是 4，[1, 3, 3, 2] 是不是先飞到 Hub 3 送货、再在 Hub 3 取货，楼主自己的测试过没过。楼主都没回。 + +【推断】OA 不要求全部测试通过：得分 8/15 的、没全过测试的都进了下一轮（评分规则未核实）。思路要对，边界要尽量补全。动手前把样例按几种读法都算一遍，再手算 m = 1、m = 2、Hub m → Hub 1、连续访问同一个 hub 这几种情况。 ## 思路 -1. **各段互相独立。** 每办完一个请求，无人机就停在那个 hub 上，所以下一段从哪里出发是确定的，和前面怎么飞无关。这样一来，总耗时的最小值 = 每一段（当前位置 → 下一个请求）各自的最短耗时之和：每一段单独取最短，不会影响别的段，所以逐段取小就是全局最优。 -2. **每一段只有两种走法。** 在耗时都非负的前提下（数据范围未核实，这里按非负算），环上从 a 到 b（a ≠ b）的最短走法要么一路顺时针，要么一路逆时针。中途掉头折返，意味着有一段路走过去又走回来；耗时非负时，这样做不会更省（最多持平），所以只需要比较两个单向的走法。本页说的「顺时针」指编号增大的方向，即 1 → 2 → … → m → 1（截图配图里的编号其实是沿逆时针方向画的，但叫法不影响答案）。 -3. **用前缀和在 O(1) 时间里求出每个方向的耗时。** 前缀和（prefix sum）是指预先算好 `pre[k] = t[1] + … + t[k]`；之后任意一段连续编号的 t 之和，都等于两个前缀和相减，所以预处理一次以后，每次求和都是常数时间。另记 `total = pre[m]`，也就是所有 t 之和。放到环上，定义 `arc(lo, hi)` 为从 lo 顺时针数到 hi（含两端）的 t 之和；lo > hi 时这段路跨过了 Hub m 到 Hub 1 那一步，和等于 `total - pre[lo-1] + pre[hi]`。下面的公式里编号要回绕（wrap around）：b−1 = 0 时取 m，a+1 或 b+1 等于 m+1 时取 1，a−1 = 0 时取 m。两种边权读法里，一条边的编号就是它对应的 t 的下标：边权（后一条）读法下，编号 i 的边连 Hub i 和 Hub i+1；边权（前一条）读法下，编号 i 的边连 Hub i−1 和 Hub i。 - - 顺时针从 a 到 b：离开耗时和边权（后一条）两种读法都是 `arc(a, b−1)`，因为一路上依次离开 a, …, b−1，经过的也正好是编号为 a, …, b−1 的边；到达耗时和边权（前一条）两种读法都是 `arc(a+1, b)`，因为一路上依次走进 a+1, …, b，经过的是编号为 a+1, …, b 的边。 - - 逆时针从 a 到 b：离开耗时是 `arc(b+1, a)`，因为依次离开 a, a−1, …, b+1；到达耗时是 `arc(b, a−1)`，因为依次走进 a−1, …, b；两种边权读法都是 `total` 减去顺时针的耗时，因为逆时针经过的正好是顺时针没经过的那些边。 -4. a == b 时这一段耗时为 0，直接跳过（为什么要专门跳过，见「易错点」）。 +1. **各段互相独立。** 每办完一个请求，无人机就停在那个 hub 上，下一段从哪出发是确定的，和前面怎么飞无关。所以每段单独取最短，互不影响，总耗时的最小值就是各段最短耗时之和。 +2. **每段只有两种走法。** 在耗时都非负的前提下（数据范围未核实，这里按非负算），环上从 a 到 b（a ≠ b）的最短走法是一路顺时针或一路逆时针。中途掉头意味着有一段路走过去又走回来，耗时非负时只会更多或持平。 +3. **朴素做法和改进。** 直接一步一步地走两个方向，每段 $O(m)$，n 段就是 $O(nm)$。按站方 AI 版本的量级（m、n 都到 $2 \times 10^5$）是 $4 \times 10^{10}$ 次，超时。改进是先算前缀和（prefix sum）： + + $$ + \text{prefix}[k] = t_1 + t_2 + \dots + t_k, \quad \text{prefix}[0] = 0 + $$ + + 之后任意一段连续编号的 t 之和都是两个前缀和相减，每段 $O(1)$。放到环上，定义 `arc_sum(lo, hi)` 为从 Hub lo 顺时针数到 Hub hi（含两端）的 t 之和。lo ≤ hi 时是 `prefix[hi] - prefix[lo-1]`。lo > hi 时这段路跨过了 Hub m → Hub 1，和是 `total - prefix[lo-1] + prefix[hi]`，其中 `total` 是全部 t 之和。 +4. **离开耗时读法下两个方向的区间。** 顺时针从 a 到 b，依次离开 a, a+1, …, b−1，耗时是 `arc_sum(a, b-1)`。逆时针从 a 到 b，依次离开 a, a−1, …, b+1，这些编号顺时针排是 b+1, …, a，耗时是 `arc_sum(b+1, a)`。编号要回绕：b−1 = 0 时取 m，b+1 = m+1 时取 1。 +5. a == b 时这一段耗时为 0，直接跳过。不跳过会出错，见「代码」里的错误版本一。 + +> [!say] After each request the drone sits at a known hub, so the segments are independent and the answer is the sum of per-segment shortest paths. With non-negative costs, the shortest way between two hubs on a ring is fully clockwise or fully counter-clockwise, so I build prefix sums once and get each direction in O(1). ## 代码 -这段代码已运行。截图样例在四种读法下分别输出 4（离开耗时）、3（到达耗时）、3（边权后一条）、4（边权前一条）；下面「测试用例」表里 7 组手算的期望值全部对上。另外还做了对拍，也就是用暴力解（brute force）在随机生成的小数据上和本解对比结果：三个暴力解、随机 3000 组数据 × 四种读法，结果全部一致。暴力解的写法见「测试用例」一节末尾。 +下面是按离开耗时读法交卷的写法。 ```python from typing import List -# transitionTime[i] 的四种读法（题面没说清，见「题目」） -MODES = ("leave", "arrive", "edge_next", "edge_prev") - - -def min_travel_time(transition_time: List[int], requested_hubs: List[int], - mode: str = "leave") -> int: - """m 个 hub 成环，无人机从 Hub 1 出发，按顺序访问 requested_hubs，返回最小总耗时。 - - hub 编号 1..m；Python 下标 transition_time[i - 1] 就是题面的 transitionTime[i]。 - mode： - "leave" ：从 Hub i 走到任一邻居花 transitionTime[i]（离开耗时，本页默认） - "arrive" ：走进 Hub i 花 transitionTime[i]（到达耗时） - "edge_next"：Hub i 与 Hub i+1 之间那条边，transitionTime[m] 连 Hub m 和 Hub 1 - "edge_prev"：Hub i-1 与 Hub i 之间那条边，transitionTime[1] 连 Hub m 和 Hub 1 - """ - if mode not in MODES: - raise ValueError(mode) + +def build_prefix(transition_time: List[int]) -> List[int]: + """prefix[k] = transitionTime[1] + ... + transitionTime[k]，prefix[0] = 0。""" + prefix = [0] * (len(transition_time) + 1) + for i, cost in enumerate(transition_time, start=1): + prefix[i] = prefix[i - 1] + cost + return prefix + + +def min_travel_time(transition_time: List[int], requested_hubs: List[int]) -> int: + """按「离开 Hub i 花 transitionTime[i]」的读法，返回从 Hub 1 出发、按顺序办完请求的最小总耗时。""" m = len(transition_time) - pre = [0] * (m + 1) # pre[k] = transitionTime[1] + ... + transitionTime[k] - for i, t in enumerate(transition_time, 1): - pre[i] = pre[i - 1] + t - total = pre[m] - - def arc(lo: int, hi: int) -> int: - """从 lo 顺时针数到 hi（含两端）的 transitionTime 之和，1 <= lo, hi <= m。""" + prefix = build_prefix(transition_time) + total = prefix[m] + + def arc_sum(lo: int, hi: int) -> int: + """从 Hub lo 顺时针数到 Hub hi（含两端）的 transitionTime 之和。""" if lo <= hi: - return pre[hi] - pre[lo - 1] - return total - pre[lo - 1] + pre[hi] # 跨过 Hub m -> Hub 1 - - def nxt(i: int) -> int: # 顺时针（编号增大）的邻居 + return prefix[hi] - prefix[lo - 1] + return total - prefix[lo - 1] + prefix[hi] # 跨过 Hub m -> Hub 1 + + def next_hub(i: int) -> int: # 顺时针邻居：m 的下一个是 1 return i % m + 1 - def prv(i: int) -> int: # 逆时针的邻居 + def prev_hub(i: int) -> int: # 逆时针邻居：1 的上一个是 m return (i - 2) % m + 1 - ans, cur = 0, 1 - for b in requested_hubs: - a = cur - if a != b: - # 顺时针 a -> a+1 -> ... -> b - if mode in ("leave", "edge_next"): - cw = arc(a, prv(b)) # 离开 a..b-1 / 走编号为 a..b-1 的边 - else: - cw = arc(nxt(a), b) # 走进 a+1..b / 走编号为 a+1..b 的边 - # 逆时针 a -> a-1 -> ... -> b - if mode == "leave": - ccw = arc(nxt(b), a) # 离开 a, a-1, ..., b+1 - elif mode == "arrive": - ccw = arc(b, prv(a)) # 走进 a-1, ..., b - else: - ccw = total - cw # 边权：逆时针正好走顺时针没走的那些边 - ans += min(cw, ccw) - cur = b - return ans + answer = 0 + current = 1 + for target in requested_hubs: + if target != current: + clockwise = arc_sum(current, prev_hub(target)) # 依次离开 current .. target-1 + counter_clockwise = arc_sum(next_hub(target), current) # 依次离开 current .. target+1 + answer += min(clockwise, counter_clockwise) + current = target + return answer if __name__ == "__main__": - t, req = [3, 2, 1], [1, 3, 3, 2] - for mode in MODES: - print(mode, min_travel_time(t, req, mode)) - # leave 4，arrive 3，edge_next 3，edge_prev 4 + print(min_travel_time([3, 2, 1], [1, 3, 3, 2])) # 4 ``` -考试时不需要四种都写：先用样例输出和样例解释（每一步的耗时）确认是哪一种读法，再把 `mode` 的分支删到只剩那一种即可。单看样例输出不够，因为它只能把四种读法分成两组（见「题目」一节）。 +### 两个错误版本 + +错误版本一去掉了 `target != current` 的判断，其余和正解相同。a == b 时，`arc_sum(a, a-1)` 和 `arc_sum(a+1, a)` 都是从一个点绕回到它前一个点，等于绕了一整圈，两个方向都是 `total`。 + +```python +def min_travel_time_no_skip(transition_time, requested_hubs): + """错误版本一：去掉了 target != current 的判断，其余和正解相同。""" + m = len(transition_time) + prefix = build_prefix(transition_time) + total = prefix[m] + + def arc_sum(lo, hi): + if lo <= hi: + return prefix[hi] - prefix[lo - 1] + return total - prefix[lo - 1] + prefix[hi] + + answer = 0 + current = 1 + for target in requested_hubs: + clockwise = arc_sum(current, (target - 2) % m + 1) + counter_clockwise = arc_sum(target % m + 1, current) + answer += min(clockwise, counter_clockwise) + current = target + return answer +``` + +错误版本二把环当成直线，只往编号的方向直接走，不走 Hub m → Hub 1 那一步。这就是旧帖说的「尾到头有坑」。 + +```python +def min_travel_time_as_line(transition_time, requested_hubs): + """错误版本二：把环当成直线，从不走 Hub m 和 Hub 1 之间那一步。""" + prefix = build_prefix(transition_time) + answer = 0 + current = 1 + for target in requested_hubs: + if target > current: # 往编号大的方向，依次离开 current .. target-1 + answer += prefix[target - 1] - prefix[current - 1] + elif target < current: # 往编号小的方向，依次离开 current .. target+1 + answer += prefix[current] - prefix[target] + current = target + return answer +``` + +2026-10-27 在 Python 3.13 上把三个函数放在同一组输入上跑： + +| 输入 | 正解 | 错误版本一 | 错误版本二 | +|---|---|---|---| +| `[3, 2, 1]`，`[1, 3, 3, 2]`（截图样例） | 4 | 16（1 → 1 和 3 → 3 各算了一整圈 6） | 6（1 → 3 只会顺时针离开 Hub 1、2，花 5） | +| `[5, 5, 5, 1]`，`[4, 1]` | 6 | 6 | 26（1 → 4 和 4 → 1 都不走 Hub 4–Hub 1 那一步） | + +第二组输入没有重复的 hub，所以错误版本一碰巧对了，靠它把错误版本二单独拎出来。随机生成 3000 组小数据和暴力解对比，错误版本一有 1803 组算错，错误版本二有 1198 组算错。 + +### 别的读法改哪两行 + +确认了读法之后，只需要改 `clockwise` 和 `counter_clockwise` 两行（编号照样回绕）： + +| 读法 | 顺时针 a → b | 逆时针 a → b | +|---|---|---| +| 离开耗时（上面的代码） | `arc_sum(a, b-1)` | `arc_sum(b+1, a)` | +| 到达耗时：依次走进 a+1, …, b 或 a−1, …, b | `arc_sum(a+1, b)` | `arc_sum(b, a-1)` | +| 边权（后一条）：经过编号 a, …, b−1 的边 | `arc_sum(a, b-1)` | `total - clockwise` | +| 边权（前一条）：经过编号 a+1, …, b 的边 | `arc_sum(a+1, b)` | `total - clockwise` | + +两种边权读法的逆时针写成 `total - clockwise`，因为逆时针经过的正好是顺时针没经过的那些边。 + +这张表的四种读法都在 2026-10-27 和暴力解对拍过。暴力解按所选读法建出有向图（每个 hub 向左右邻居各连一条边，m = 2 时两条边分开算），用 Dijkstra 和 Floyd–Warshall 两种最短路算法各算一遍，按请求顺序累加。图上的最短路允许任意折返，所以对拍也检验了思路第 2 步「每段只比较两个方向」。随机 3000 组（m 取 1–7，n 取 0–8，单个耗时取 0–6，含 0），四种读法下前缀和解和两个暴力解全部一致。 + +> [!say] Clockwise is always one prefix-sum range. Counter-clockwise is another range for the node readings, or the total minus clockwise for the edge readings. Then I handle the wrap from hub m back to hub 1 and repeated hubs. ## 复杂度 -时间复杂度是 O(m + n)，其中前缀和预处理是 O(m)，每个请求只做常数次计算，是 O(1)。空间复杂度是 O(m)，用来存前缀和数组。在本机上取 m = n = 2×10^5 跑，每种读法大约 0.13–0.18 秒。 +时间 $O(m + n)$：前缀和 $O(m)$，每个请求常数次计算。空间 $O(m)$，存前缀和。2026-10-27 用 m = n = $2 \times 10^5$、单个耗时取 1 到 $10^9$ 的随机数据跑正解，耗时 0.24 秒。 ## 易错点 -- **先确定 transitionTime 的含义。** 「题目」一节的表说明了，样例只能把四种读法分成两组。还要注意，离开耗时、到达耗时这两种读法下，a → b 和 b → a 的耗时可以不一样（例如 t = [1, 10, 1, 1]，按离开耗时，1 → 2 花 1，2 → 1 花 10），不能想当然地认为来回对称。 -- **起点是 Hub 1**，不是 requestedHubs[0]。站方 AI 版本里有一份写成从 requestedHubs[0] 出发，和截图冲突。 -- **连续访问同一个 hub 时**（样例里的 3, 3），这一段耗时是 0，要先判断 a == b 并跳过。如果用上面的 `arc` 写法却不做这个判断，离开耗时、到达耗时两种读法会把 a == b 当成绕了一整圈，样例会分别算出 16 和 15。两种边权读法用 `total` 减去顺时针耗时来算逆时针，恰好得到 0，所以不判断也对；但先判断更稳，因为结果就不依赖公式在这个边界上恰好成立。 -- **编号从 1 开始，环首尾相连。** Python 列表的下标要减一；编号回绕时，0 要换成 m，m+1 要换成 1。楼主转引的一亩三分地旧帖专门提到，从尾部出发去头部的那一步有坑，楼主自己也提醒要切记头尾相连。 -- **m = 2 时**，两个方向到的是同一个邻居。离开耗时、到达耗时两种读法下，两条路的耗时一样；两种边权读法下，两条路是两条不同的边 t[1] 和 t[2]，要取较小的那个。有位楼主得分 8/15，提到 m = 2 的环形边界情况没解决，原帖没说具体错在哪（未核实）。【推断】常见的坑有两个：一是按「左邻居、右邻居」建邻接表（adjacency list）时，两个邻居其实是同一个点，边权读法下后写进去的那条边会把先写的覆盖掉；二是取模回绕时下标算错。 -- **m = 1 时**，请求只能是 Hub 1，答案是 0。这时唯一的那个 hub 左右两边的「邻居」都是它自己，但每一段都是 a == b，前面的判断已经直接跳过，根本用不到邻居，所以不必为此专门给它建一条连向自己的边（自环，self-loop）。 -- **注意溢出（overflow）。** Java 要用 `long`，C++ 要用 `long long`（或 `int64_t`）。C++ 不能用 `long` 代替，因为 `long` 的位数由编译器决定，Windows 上的 MSVC 编译器采用 LLP64 数据模型，`long` 只有 32 位。站方 AI 版本写的数据范围是最多 2×10^5 个 hub、单个耗时 10^9（站方 AI 整理，未经原帖证实）；按这个量级，前缀和 `pre` 和答案都可能超出 int：只要三个 10^9 相加，就超过了 int 的上限 2^31 − 1（约 2.1×10^9）。 +- **连续访问同一个 hub**：不跳过 a == b 会被算成绕一整圈，样例从 4 变成 16（「代码」错误版本一）。 +- **Hub m → Hub 1 要回绕**：当成直线算，`[5, 5, 5, 1]`、`[4, 1]` 从 6 变成 26（错误版本二）。下标 0 换成 m，m+1 换成 1。 +- **起点是 Hub 1**，不是 `requestedHubs[0]`。站方 AI 版本里有一份写成从 `requestedHubs[0]` 出发，和截图冲突。 +- **m = 2**：两个方向到的是同一个邻居。离开耗时读法下两条路一样贵，边权读法下是 t[1] 和 t[2] 两条不同的边，要取较小的。有位楼主卡在 m = 2 上，原帖没说具体错在哪。【推断】常见的坑是按「左邻居、右邻居」建邻接表时两个邻居是同一个点，边权读法下后写进去的边把先写的覆盖了。前缀和写法不建邻接表，没有这个问题，表里 `[4, 9]`、`[2, 1, 2]` 这组覆盖了它。 +- **溢出**：Python 不用管。Java 用 `long`，C++ 用 `long long`。上面 0.24 秒那组数据的答案约 $5 \times 10^{18}$，远超 32 位整数上限 $2^{31} - 1$。按站方 AI 版本的量级，最坏情况（全部耗时 $10^9$，请求在 Hub 1 和正对面的 Hub $10^5 + 1$ 之间来回）答案是 $2 \times 10^{19}$，连 64 位有符号整数的上限（约 $9.2 \times 10^{18}$）也超了。这个量级未经原帖证实，真题的范围多半更小，考试时看题面写的范围（未核实）。 + +> [!optional] C++ 里不要用 `long` 代替 `long long`：Windows 上的 MSVC 编译器用 LLP64 数据模型，`long` 只有 32 位。 ## 测试用例 -| transitionTime | requestedHubs | 离开耗时（默认） | 到达耗时 | 边权（后一条） | 边权（前一条） | 说明 | +2026-10-27 跑过，正解一列就是上面的代码，另外三列用「改哪两行」那张表改出来的版本： + +| transitionTime | requestedHubs | 离开耗时（正解） | 到达耗时 | 边权（后一条） | 边权（前一条） | 测的是 | |---|---|---|---|---|---|---| | [3, 2, 1] | [1, 3, 3, 2] | 4 | 3 | 3 | 4 | 截图样例 | -| [3, 2, 1] | [2] | 3 | 2 | 3 | 2 | 起点是 Hub 1，第一个请求不是 1 | -| [5, 5, 5, 1] | [4, 1] | 6 | 6 | 2 | 10 | 头尾相连：1 → 4、4 → 1 都走 Hub 4–Hub 1 那一步 | +| [3, 2, 1] | [2] | 3 | 2 | 3 | 2 | 起点是 Hub 1 | +| [5, 5, 5, 1] | [4, 1] | 6 | 6 | 2 | 10 | Hub 4 和 Hub 1 之间的回绕 | | [7] | [1, 1, 1] | 0 | 0 | 0 | 0 | m = 1 | | [4, 9] | [2, 1, 2] | 17 | 22 | 12 | 12 | m = 2 | | [1, 2, 3] | [] | 0 | 0 | 0 | 0 | 没有请求 | -| [1, 10, 1, 1] | [2, 1] | 11 | 11 | 2 | 6 | 方向不对称；同组的两种读法在这里分开 | - -### 对拍用的暴力解 - -上面的代码还和三个暴力解做了对拍，也就是在随机生成的小数据上对比结果。其中两个暴力解显式建出有向图（directed graph）：每个 hub i 向 i±1 连边，边的权重按所选读法给（m = 2 时两个方向算两条不同的边），再分别用 Floyd（Floyd–Warshall，求所有点对之间的最短路）和 Dijkstra（求单源最短路）算出最短路，按请求顺序累加。图上的最短路允许任意折返，所以这两个暴力解不依赖「每段只在两个方向里取小」这个结论，能独立地检验它。第三个暴力解分别一步一步走完顺时针、逆时针两条路，再取较小的那个；它本身就用了「两个方向取小」，检验的是前缀和公式和编号回绕有没有算错。随机生成了 3000 组数据（m 取 1–7、n 取 0–8、单个耗时取 0–6，包含 0），四种读法下，本页的解和三个暴力解的结果全部一致。 +| [1, 10, 1, 1] | [2, 1] | 11 | 11 | 2 | 6 | 来回不对称，同组两种读法分开 | + +最后一行说明离开耗时和到达耗时两种读法下 a → b 和 b → a 可以不一样贵：离开耗时下 1 → 2 花 1，2 → 1 花 10。 ## Follow-up -- **如果只许顺时针飞。** 有一篇帖子写的是无人机顺时针送快递（那篇说自己做过模糊处理，原题是不是这样未核实）。真这样考的话，每一段直接取顺时针那一项，不再和逆时针比较取小。 -- **LeetCode 1184 原题。** 它只问一次两点之间的最短距离，相当于上面单独一段的计算（按边权读法）。有楼主说这道题像它的变形。 - -下面两条是本页自己设想的延伸问题，面经里没有见到过： - -- **transitionTime 会被在线修改**，修改和查询穿插进行。这时普通的前缀和不够用：改一个值要更新它后面所有的前缀和，是 O(m)。可以换成树状数组（Fenwick tree，也叫 binary indexed tree），单点修改和前缀求和都是 O(log m)。 -- **要求输出每一段往哪个方向飞。** 比较两个方向时，顺便记下顺时针、逆时针哪个更小即可。 - -## 英文讲法 - -> [!say] After each request the drone sits at a known hub, so the segments are independent and the answer is just the sum of per-segment shortest paths. On a ring with non-negative costs, the shortest way between two hubs is either fully clockwise or fully counter-clockwise, so I build prefix sums once and get each direction in O(1). - -> [!say] The one subtle point is what transitionTime[i] means: the cost of leaving hub i, the cost of entering it, or the weight of the edge on one side of it. The sample output only narrows it down to two readings, so I'd confirm with the sample explanation before coding. Clockwise is always one prefix-sum range; counter-clockwise is either another range or, for the edge readings, just the total minus clockwise. Then I handle the wrap from hub m back to hub 1, repeated hubs, and m = 1 or 2. +- **只许顺时针飞。** 有一篇帖子这样写（那篇说做过模糊处理，原题是不是这样未核实）。每段直接取 `clockwise`，去掉和逆时针取小那一步。思路第 1 步的独立性照样成立，复杂度不变。 +- **LeetCode 1184 原题。** 1184 给的是相邻两站之间的距离，只问一次两站的最短距离，相当于本题按边权（后一条）读法单独算一段：`min(clockwise, total - clockwise)`，前缀和都不用建，扫一遍求和即可，$O(m)$。
meta
@@ -1 +1,5 @@ -{} +{ + "depth_guide": "2026-10-23", + "rewritten_by": "cloud:20261026-2313", + "rewritten_at": "2026-10-27" +}