相遇折返等价于互相穿过并交换身份,名次永不改变,问题化为在两个有序数组的并中二分求第 r 小值
OJ: roj
题目 ID: 5014
难度:提高+/省选-
标签:二分排序思维
创建: 2026-10-08 14:40
更新: 2026-10-08 14:40
形式化题目
在无限长数轴上有
给定
数据范围:
正解
思路
朴素想法:直接模拟折返过程 —— 找出下一次相遇时刻、交换两人的朝向,一直推到
关键洞察一:相遇折返 ≡ 穿过对方并交换身份。 两个孩子迎面相遇时同时折返,此后各自走的路线,与「两人互不干扰地穿过对方、继续按原方向走」在每一时刻的位置集合上完全一致 —— 唯一的区别只是「谁在这条路线上的名字」不同。换一种说法:把孩子想成拿着号码牌的粒子,相遇折返的物理过程等价于粒子互相穿过、并在相遇瞬间交换号码牌。
关键洞察二:按初始位置排序的名次永不改变。 在折返模型里孩子之间无法互相穿越(相遇只会掉头,不会越过),因此任意时刻从左到右的第
由这两点立刻得到:任意时刻
即「每个人都按初始方向不回头地走到
于是问题变成两步:
-
预处理:按初始位置把孩子升序排序,记录每个孩子(按输入编号
)的名次 rank_of[k](起),并把向右走的初始位置收集为升序数组 right_pos、向左走的收集为升序数组left_pos(由于是按位置升序遍历时顺手收集的,两个数组天然有序)。 -
每次询问
:求两个有序数组 合并后的第
小值。注意 与 各自仍是有序的( 、 都是保序变换),所以可以二分划分求第 小。
求两个有序数组的第 right_pos 里取前 left_pos 里取前
合法时答案就是左半部分的最大值
- 若
,说明从 right 里取多了,令 hi = x - 1; - 否则若
,说明取少了,令 lo = x + 1; - 否则划分合法,返回答案。
越界处(
由于位置互不相同但 max(r_last, l_last) 仍返回正确坐标。
代码
#!/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()/**
* 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;
}复杂度
- 时间复杂度:排序
;每次询问二分一次划分, ,共 。总计 ,对 绰绰有余(实测 Python 最慢约 秒,C++ 约 秒)。 - 空间复杂度:存孩子信息、两个方向的有序位置数组与名次映射,
。
总结
-
「相遇折返 ≡ 穿过对方」为什么成立:所有孩子速度大小恒为
,迎面相遇时双方同时掉头,之后各自走过的路线与「两人直接穿过对方、原方向匀速直走」完全重合 —— 唯一差别是两条路线上的「名字」互换了,即穿过对方的瞬间交换了号码牌。因此每一时刻的位置多重集合与「无碰撞直走」模型完全一致,我们才能写出 。 -
「名次不变」正是第
小化归的依据:在折返模型中孩子永远不会互相穿越(相遇只会掉头),所以从左到右的名次序是不变量;等价地,在「交换号码牌」视角下,名次就是号码牌的传递载体 —— 穿过不改变「第 个位置上有一个孩子」这一事实。于是「编号 的孩子 秒后在哪」就等于「 中第 小的值是多少」,其中 是孩子 按初始位置排序的名次。位置的多重集合恒为 ,这就是整个化归的合法性来源。 -
为什么不能每次询问都排序:
可达 ,若对每个询问把 全部算出来再排序,单次 ,总 ,必然超时。正确做法是注意到 是两个有序数组的并( 升序、 升序, 保序),对划分点 二分即可 求出第 小。 -
64 位整数必要性:
与 都可达 , 可达 , int存不下;哨兵更必须是 64 位。C++ 中坐标、时间与中间量一律用 long long(scanf/printf用lld);Python 的int任意精度,天然安全。 -
易踩的坑:「名次」≠ 孩子编号。询问给的
是输入顺序中的编号,要先用预处理出的 rank_of[k]换成按初始位置排序的名次(本实现从起),再去 里取第 小;直接拿 当名次用是最典型的错误。另外答案可能是负数(孩子走出桥外仍在运动),不要按「桥长」之类的假设截断。
补充说明:Python 实现中使用了 type Positions = list[int] 类型别名语法,需要 Python 3.12+;若评测环境版本更老,把它删掉即可,不影响算法。数据本身经核对无缺陷:10 个点的全部答案都落在 std.cpp 输出与 .out 逐字节一致;两份实现对三份独立暴力(含一份完全不用「名次不变」结论的事件驱动模拟)411 组小数据 + 46 组边界用例 0 分歧。