米哈游 10 月 11 日机考笔试：分拣中心最少跳转次数

《面试题目》

1. 第 1 题「分拣中心」：某快递分拣中心有 m 个分拣口，编号从 1 到 m，包裹一开始放在 1 号口，需要送到 m 号口。每个分拣口都配置了一条传送带：若包裹当前停在第 i 号口，可以支付 1 次跳转费用，把它送到闭区间 [a_i, b_i] 内的任意一个分拣口，也就是说可以选择任意整数 j 满足 a_i ≤ j ≤ b_i。请计算把包裹从 1 号口送到 m 号口最少需要几次跳转，若怎样跳都到不了则视为无解。输入第一行是整数 g（1 ≤ g ≤ 2×10^5），表示询问组数；接着是 g 组数据，每组第一行是整数 m（1 ≤ m ≤ 2×10^5），第二行是 m 个整数 a_1 到 a_m，第三行是 m 个整数 b_1 到 b_m；保证对每个 i 都有 1 ≤ a_i ≤ b_i ≤ m，且同一文件内所有 m 之和不超过 4×10^5。输出一行 g 个整数，相邻整数用单个空格隔开，第 t 个数表示第 t 组询问的最少跳转次数，无法送达则输出 -1。样例中 m = 6、a = [2,3,5,6,6,6]、b = [4,5,6,6,6,6] 的答案是 2（一条最优路线是 1 → 3 → 6），而 m = 4、a = [1,1,1,4]、b = [2,2,2,4] 的答案是 -1（只能一直在 1 和 2 之间往返），m = 1 时起点即终点，答案是 0。

《参考解析》

先把它看成一张图：这是无权最短路

把每个分拣口当作图上的一个节点，从节点 i 向区间 [a_i, b_i] 内的每一个 j 连一条有向边，边权都是 1，那么「最少跳转次数」就是从 1 号点到 m 号点的最短路径长度，无解就是不可达。因为边权全为 1，用 BFS 而不是 Dijkstra；BFS 的第一次入队即最短路，这个性质是后面所有优化的前提，也是为什么可以给节点做「访问过就永久删除」这种激进的剪枝。

朴素做法的问题出在边数上：每个节点最多连出 m 条边，整张图最坏有 O(m²) 条边，而 m 可以到 2×10^5。无论是显式建图还是每次遍历整段区间，都必然超时。所以这道题的分数几乎全部落在「怎么不把区间展开成边」这一步上，题面本身反而没什么坑。

核心优化：并查集维护「下一个还没访问过的点」

优化的出发点是一句很朴素的话：一个点一旦被 BFS 访问过，它的最短路就确定了，之后再被别的区间覆盖到也不会更优，所以可以从「尚未访问」的集合里永久删掉。于是「枚举区间里的每一个点」被改写成「反复取区间里第一个还没被访问的点，取完立刻删掉它」，具体用并查集做后继指针：

• find(x) 返回编号不小于 x 的第一个未访问节点；
• 初始时每个点指向自己；访问掉点 v 之后令 parent[v] = find(v + 1)，让后续搜索跳过 v；
• BFS 每次从队列取出 u，从 v = find(a[u]) 开始循环，只要 v <= b[u] 就处理 v——记下 dist[v] = dist[u] + 1、把 v 入队、再把它从集合里删掉——然后 v = find(v) 继续取下一个。

每个点最多入队一次、最多被删除一次，路径压缩之后的 find 近似常数时间，总复杂度 O(m·α(m))，通常直接写成 O(m)；所有询问合计 O(sum(m)·α(sum(m)))，对 4×10^5 的总规模来说非常宽裕。空间上只需要并查集、距离数组和 BFS 队列，都是 O(m)。

实现细节：几个几乎一定会踩的坑

第一，起点必须先标记成已访问。原帖代码里那句 parent[1] = find(2) 干的就是这件事：如果不做，某条传送带的区间一旦覆盖到 1 号口，起点会被重新入队，距离被覆盖成非零值，轻则答案偏大，重则队列里反复刷 1 而出不来。

第二，哨兵要留够。并查集数组开到 m + 2，并且要保证 find(m + 1) 返回 m + 1 自己，这样 v <= b[u] 的循环条件会自然终止，不会把下标推到数组外面。循环体里「先删除 v、再取下一个」这个顺序也不能颠倒，v = find(v) 依赖的正是「被删掉的 v 已经指向它的后继」。

第三，m = 1 要单独判 0，起点即终点一次都不用跳。不特判的话，BFS 从 1 出发却永远「看不到」m（因为 1 已经被标记访问），最后会落到返回 -1 的分支上。

第四，多组询问不要反复清空大数组。每组按当组的 m 现分配，总代价才是 O(sum(m))；如果每组都开一个 4×10^5 的数组清零，g 大了以后会退化成 O(g·m)，比没优化还慢。

第五，也是最容易走偏的一点：别把它做成贪心。「每次跳到当前区间能到达的最远点」听上去很合理，但 b_j 关于 j 并不单调。反例很好构造：从 1 号口可以到 2 或 3，2 号口的区间只能到 10，而 3 号口只能在 3 待着——跳到最远的 3 反而走不动，正确答案是 1 → 2 → 10 两次跳转。区间连边的最短路没有这种单调性，所以只能老老实实 BFS。

复杂度与可选方案对比

时间复杂度 O(m·α(m))，空间 O(m)。同类题还有两种常见写法可以对照着讲，面试官问「还有别的做法吗」时能接得住：一是线段树优化建图，把每个区间连边拆成 O(log m) 条有向边，再跑 0-1 BFS 或普通 BFS，复杂度 O(m log m)，代价是要多开一倍的辅助节点、代码量明显变大；二是老老实实对每张传送带做一次区间松弛，那是 O(m²)，只能过很小的数据。本题因为有「每个点只会入队一次」这个性质，并查集跳点是最短、常数最小的写法——能说清「为什么可以不枚举区间里的点」，比背下一个模板更有说服力。