独木桥

GitHub跳转原题关系图返回列表

相遇折返等价于互相穿过并交换身份,名次永不改变,问题化为在两个有序数组的并中二分求第 r 小值

OJ: roj

题目 ID: 5014

难度:提高+/省选-

标签:二分排序思维

创建: 2026-10-08 14:40

更新: 2026-10-08 14:40

形式化题目

在无限长数轴上有 nn 个孩子,初始位于 nn 个互不相同的整点 pip_i 上,各有一个初始朝向 di∈{0,1}d_i \in \{0,1\}(11 向右、00 向左)。所有孩子始终以每秒 11 单位长度的速度沿当前朝向匀速运动;每当某一时刻若干个孩子同时到达同一位置,他们立即各自反转朝向并继续运动。

给定 qq 次询问,每次给定 kik_i 与 tit_i,求输入顺序中编号为 kik_i(从 00 开始)的孩子在 tit_i 秒后所在的坐标。孩子走出「桥」外仍在数轴上运动,答案可以是负数。

数据范围:1≤n,q≤2×1051 \le n, q \le 2 \times 10^5,0≤ki<n0 \le k_i < n,0≤pi,ti≤1090 \le p_i, t_i \le 10^9,di∈{0,1}d_i \in \{0,1\}。

正解

思路

朴素想法:直接模拟折返过程 —— 找出下一次相遇时刻、交换两人的朝向,一直推到 tt 秒。问题在于相遇事件可能极多(nn 个孩子两两交错时事件数可达 O(n2)O(n^2)),更糟的是每次询问的 tit_i 不同,模拟无法在所有询问间共享结果。这条路走不通,必须找「运动过程的不变量」。

关键洞察一:相遇折返 ≡ 穿过对方并交换身份。 两个孩子迎面相遇时同时折返,此后各自走的路线,与「两人互不干扰地穿过对方、继续按原方向走」在每一时刻的位置集合上完全一致 —— 唯一的区别只是「谁在这条路线上的名字」不同。换一种说法:把孩子想成拿着号码牌的粒子,相遇折返的物理过程等价于粒子互相穿过、并在相遇瞬间交换号码牌。

关键洞察二:按初始位置排序的名次永不改变。 在折返模型里孩子之间无法互相穿越(相遇只会掉头,不会越过),因此任意时刻从左到右的第 rr 个位置上坐的一定是同一个「名次」的孩子(具体是哪个孩子会因交换身份而变化,但名次对应的位置序不变)。注意这里的「名次」是按初始位置升序排出来的名次,不是孩子的输入编号。

由这两点立刻得到:任意时刻 tt,所有孩子占据的坐标多重集合恒等于

St={ pi+t∣di=1 }  ∪  { pi−t∣di=0 }, S_t = \{\, p_i + t \mid d_i = 1 \,\} \;\cup\; \{\, p_i - t \mid d_i = 0 \,\},

即「每个人都按初始方向不回头地走到 pi±tp_i \pm t」。而初始名次为 rr(从 11 开始)的孩子,tt 秒后恰好位于 StS_t 的第 rr 小值处。

于是问题变成两步:

  1. 预处理:按初始位置把孩子升序排序,记录每个孩子(按输入编号 kk)的名次 rank_of[k](11 起),并把向右走的初始位置收集为升序数组 right_pos、向左走的收集为升序数组 left_pos(由于是按位置升序遍历时顺手收集的,两个数组天然有序)。

  2. 每次询问 (k,t)(k, t):求两个有序数组

    R={right_pos[i]+t},L={left_pos[j]−t}R = \{\texttt{right\_pos}[i] + t\}, \qquad L = \{\texttt{left\_pos}[j] - t\}

    合并后的第 rank_of[k]\texttt{rank\_of}[k] 小值。注意 RR 与 LL 各自仍是有序的(+t+t、−t-t 都是保序变换),所以可以二分划分求第 rr 小。

求两个有序数组的第 rr 小(划分二分):设答案的划分是从 right_pos 里取前 xx 个、从 left_pos 里取前 y=r−xy = r - x 个进入「左半部分」。合法划分需要

right_pos[x−1]+t≤left_pos[y]−t且left_pos[y−1]−t≤right_pos[x]+t. \texttt{right\_pos}[x-1] + t \le \texttt{left\_pos}[y] - t \quad\text{且}\quad \texttt{left\_pos}[y-1] - t \le \texttt{right\_pos}[x] + t .

合法时答案就是左半部分的最大值 max⁡(right_pos[x−1]+t, left_pos[y−1]−t)\max(\texttt{right\_pos}[x-1]+t,\ \texttt{left\_pos}[y-1]-t)。xx 的合法范围是 [max⁡(0,r−left_cnt), min⁡(r,right_cnt)][\max(0, r-\texttt{left\_cnt}),\ \min(r, \texttt{right\_cnt})],在此区间上二分:

  • 若 right_pos[x−1]+t>left_pos[y]−t\texttt{right\_pos}[x-1]+t > \texttt{left\_pos}[y]-t,说明从 right 里取多了,令 hi = x - 1;
  • 否则若 left_pos[y−1]−t>right_pos[x]+t\texttt{left\_pos}[y-1]-t > \texttt{right\_pos}[x]+t,说明取少了,令 lo = x + 1;
  • 否则划分合法,返回答案。

越界处(x=0x=0、x=right_cntx=\texttt{right\_cnt} 等)用哨兵 ±INF\pm\text{INF}(代码取 ±4×1018\pm 4\times 10^{18})代替,保证比较不会误判;由于 ∣p±t∣≤2×109≪4×1018|p \pm t| \le 2\times 10^9 \ll 4\times 10^{18},哨兵不会与真实值混淆。实现上(两份代码一致)是「先取 x=⌊(lo+hi)/2⌋x = \lfloor(\texttt{lo}+\texttt{hi})/2\rfloor 检查划分,不合法则按上述方向收缩」,单次 O(log⁡n)O(\log n)。

由于位置互不相同但 StS_t 中可能出现相等值(例如 pj−pi=2tp_j - p_i = 2t),此时「第 rr 小」的相邻取值相等,max(r_last, l_last) 仍返回正确坐标。

代码

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 14:12
# update_at: 2026-10-08 14:27

import sys

INF = 4 * 10**18  # 划分二分的哨兵:p±t 的绝对值都远小于它

type Positions = list[int]  # 某个方向(向右 / 向左)的全部初始位置,升序


def kth_after_time(right_pos: Positions, left_pos: Positions, rank: int, t: int) -> int:
    """求 {right_pos[i]+t} ∪ {left_pos[j]-t} 合并后的第 rank 小(rank 从 1 开始)。

    枚举「从 right_pos 里取 x 个」,二分找让两侧划分合法的 x,O(log n)。
    """
    right_cnt, left_cnt = len(right_pos), len(left_pos)
    lo, hi = max(0, rank - left_cnt), min(rank, right_cnt)
    while lo <= hi:
        x = (lo + hi) // 2
        y = rank - x
        # 划分点两侧的四个边界值,越界处用哨兵保证比较不会误判
        r_last = right_pos[x - 1] + t if x > 0 else -INF
        r_next = right_pos[x] + t if x < right_cnt else INF
        l_last = left_pos[y - 1] - t if y > 0 else -INF
        l_next = left_pos[y] - t if y < left_cnt else INF
        split_ok = r_last <= l_next and l_last <= r_next
        if split_ok:
            return max(r_last, l_last)  # 划分合法时第 rank 小就是左半部分的最大值
        if r_last > l_next:
            hi = x - 1  # right_pos 取多了
        else:
            lo = x + 1  # right_pos 取少了
    return 0


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    try:
        n = next(data)
    except StopIteration:
        return
    pos = [next(data) for _ in range(n)]
    d = [next(data) for _ in range(n)]
    q = next(data)

    # 相遇折返等价于互相穿过并交换身份:位置多重集不变,且按初始位置的
    # 名次在任何时刻都不变,所以按位置升序排一遍即可确定每个方向的升序数组。
    order = sorted(range(n), key=pos.__getitem__)
    rank_of = [0] * n                                   # rank_of[k]:孩子 k 的名次,从 1 开始
    for r, k in enumerate(order, 1):
        rank_of[k] = r
    right_pos: Positions = [pos[k] for k in order if d[k] == 1]
    left_pos: Positions = [pos[k] for k in order if d[k] == 0]

    out: list[str] = []
    for _ in range(q):
        k, t = next(data), next(data)
        out.append(str(kth_after_time(right_pos, left_pos, rank_of[k], t)))
    sys.stdout.write("\n".join(out) + "\n")


if __name__ == "__main__":
    solve()
cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-08 14:12
 * update_at: 2026-10-08 14:27
 */
// 一本通 1678《独木桥》
// 相遇折返 <=> 互相穿过并交换身份:位置的多重集 = {p_i+t : d_i=1} ∪ {p_i-t : d_i=0}
// 折返模型里点与点永不互相穿越,所以按初始位置排序的名次在任何时刻都不变,
// 初始名次为 r 的孩子,t 秒后就位于该多重集的第 r 小值处。
// 每个询问用「两个有序数组的划分」二分求第 r 小,O(log n),总复杂度 O((n+q)log n)。
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long ll;

const int MAXN = 200005;    // n, q <= 2*10^5
const ll INF = 4000000000000000000LL;  // 划分二分的哨兵:p±t 的绝对值都远小于它

struct Child {
    ll p;   // 初始位置
    int d;  // 初始朝向:1 向右,0 向左
    int id; // 输入顺序里的编号
};

Child child[MAXN];      // child[]:所有孩子按初始位置升序排列
ll right_pos[MAXN];     // 初始向右走的孩子位置,升序
ll left_pos[MAXN];      // 初始向左走的孩子位置,升序
int rank_of[MAXN];      // rank_of[k]:孩子 k 按初始位置升序的名次,从 1 开始
int right_cnt, left_cnt;

// 按初始位置升序排列孩子
bool cmp_by_pos(const Child &a, const Child &b) {
    return a.p < b.p;
}

// 求 {right_pos[i]+t} ∪ {left_pos[j]-t} 合并后的第 rank 小(rank 从 1 开始)
// 枚举「从 right 里取 x 个」,检查 x 是否让两个数组的划分合法,不合法就二分收缩。
ll kth_after_time(ll t, int rank) {
    int lo = max(0, rank - left_cnt);
    int hi = min(rank, right_cnt);
    while (lo <= hi) {
        int x = (lo + hi) / 2;
        int y = rank - x;
        // 划分点两侧的四个边界值,越界处用哨兵保证比较不会误判
        ll r_last = (x > 0) ? right_pos[x - 1] + t : -INF;
        ll r_next = (x < right_cnt) ? right_pos[x] + t : INF;
        ll l_last = (y > 0) ? left_pos[y - 1] - t : -INF;
        ll l_next = (y < left_cnt) ? left_pos[y] - t : INF;
        if (r_last <= l_next && l_last <= r_next) {
            return max(r_last, l_last);   // 合法划分,第 rank 小就是左半部分的最大值
        }
        if (r_last > l_next) {
            hi = x - 1;                   // right 取多了
        } else {
            lo = x + 1;                   // right 取少了
        }
    }
    return 0;
}

void solve() {
    int n;
    if (scanf("%d", &n) != 1) return;

    for (int i = 0; i < n; i++) {
        scanf("%lld", &child[i].p);
        child[i].id = i;
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &child[i].d);
    }

    sort(child, child + n, cmp_by_pos);

    for (int i = 0; i < n; i++) {
        rank_of[child[i].id] = i + 1;
        if (child[i].d == 1) {
            right_pos[right_cnt++] = child[i].p;
        } else {
            left_pos[left_cnt++] = child[i].p;
        }
    }

    int q;
    if (scanf("%d", &q) != 1) return;

    while (q--) {
        int k;
        ll t;
        scanf("%d %lld", &k, &t);
        printf("%lld\n", kth_after_time(t, rank_of[k]));
    }
}

int main() {
    solve();
    return 0;
}

复杂度

  • 时间复杂度:排序 O(nlog⁡n)O(n \log n);每次询问二分一次划分,O(log⁡n)O(\log n),共 O(qlog⁡n)O(q \log n)。总计 O((n+q)log⁡n)O((n+q)\log n),对 n,q≤2×105n, q \le 2\times 10^5 绰绰有余(实测 Python 最慢约 0.560.56 秒,C++ 约 0.070.07 秒)。
  • 空间复杂度:存孩子信息、两个方向的有序位置数组与名次映射,O(n)O(n)。

总结

  1. 「相遇折返 ≡ 穿过对方」为什么成立:所有孩子速度大小恒为 11,迎面相遇时双方同时掉头,之后各自走过的路线与「两人直接穿过对方、原方向匀速直走」完全重合 —— 唯一差别是两条路线上的「名字」互换了,即穿过对方的瞬间交换了号码牌。因此每一时刻的位置多重集合与「无碰撞直走」模型完全一致,我们才能写出 St={pi+t}∪{pi−t}S_t = \{p_i+t\} \cup \{p_i-t\}。

  2. 「名次不变」正是第 rr 小化归的依据:在折返模型中孩子永远不会互相穿越(相遇只会掉头),所以从左到右的名次序是不变量;等价地,在「交换号码牌」视角下,名次就是号码牌的传递载体 —— 穿过不改变「第 rr 个位置上有一个孩子」这一事实。于是「编号 kk 的孩子 tt 秒后在哪」就等于「StS_t 中第 rr 小的值是多少」,其中 rr 是孩子 kk 按初始位置排序的名次。位置的多重集合恒为 StS_t,这就是整个化归的合法性来源。

  3. 为什么不能每次询问都排序:qq 可达 2×1052\times 10^5,若对每个询问把 StS_t 全部算出来再排序,单次 O(nlog⁡n)O(n \log n),总 O(qnlog⁡n)O(qn \log n),必然超时。正确做法是注意到 StS_t 是两个有序数组的并(R={pi+t}R = \{p_i + t\} 升序、L={pi−t}L = \{p_i - t\} 升序,±t\pm t 保序),对划分点 xx 二分即可 O(log⁡n)O(\log n) 求出第 rr 小。

  4. 64 位整数必要性:pip_i 与 tt 都可达 10910^9,pi+tp_i + t 可达 2×1092\times 10^9,int 存不下;哨兵 ±INF=±4×1018\pm\text{INF} = \pm 4\times 10^{18} 更必须是 64 位。C++ 中坐标、时间与中间量一律用 long long(scanf/printf 用 lld);Python 的 int 任意精度,天然安全。

  5. 易踩的坑:「名次」≠ 孩子编号。询问给的 kk 是输入顺序中的编号,要先用预处理出的 rank_of[k] 换成按初始位置排序的名次(本实现从 11 起),再去 StS_t 里取第 rr 小;直接拿 kk 当名次用是最典型的错误。另外答案可能是负数(孩子走出桥外仍在运动),不要按「桥长」之类的假设截断。

补充说明:Python 实现中使用了 type Positions = list[int] 类型别名语法,需要 Python 3.12+;若评测环境版本更老,把它删掉即可,不影响算法。数据本身经核对无缺陷:10 个点的全部答案都落在 StS_t 内,素材 std.cpp 输出与 .out 逐字节一致;两份实现对三份独立暴力(含一份完全不用「名次不变」结论的事件驱动模拟)411 组小数据 + 46 组边界用例 0 分歧。