题目理解与问题转化

我们有一个一维数轴，Bajtazar 从位置 0 出发，速度 ≤ 1。有 n 颗流星会在特定时间 tᵢ 砸到特定位置 xᵢ。Bajtazar 希望在每个流星坠落时刻，自己离那颗流星的距离都尽可能远。目标是最大化所有流星坠落时刻中，他离最近流星的最小距离。

换句话说，我们想找一个最大的 d，使得存在一条运动轨迹，在每个时间 tᵢ，Bajtazar 的位置 y(tᵢ) 满足：

[ |y(t_i) - x_i| \ge d \quad \forall i ]

并且他的运动满足 |y(t) - y(s)| ≤ |t - s|（速度限制）。

核心思路：二分答案

这是一个典型的最大化最小值问题，通常用二分答案解决：

1. 二分可能的距离 d。
2. 对于每个候选的 d，判断是否存在满足速度限制的路径，使得在每个 tᵢ 时刻，Bajtazar 的位置距离 xᵢ 至少为 d。
3. 如果存在，说明 d 可行，可以尝试更大的 d；否则需要减小 d。

可行性检查的关键

对于给定的 d，如何判断是否存在满足条件的路径？

1. 运动的速度限制与可达区域

如果 Bajtazar 在时间 t₀ 位于位置 p₀，那么在时间 t（t ≥ t₀），他能够到达的位置范围是：

[ [p₀ - (t - t₀),\ p₀ + (t - t₀)] ]

这是由最大速度 1 决定的。

2. 流星带来的约束

在流星坠落时刻 tᵢ，Bajtazar 必须避开以 xᵢ 为中心、半径为 d 的区域：

[ \text{禁止区域} = [x_i - d,\ x_i + d] ]

他必须位于这个区间的补集中。

3. 维护可行位置区间

我们可以按时间顺序处理流星事件，维护 Bajtazar 在每个时间段的可能位置集合。

实际上，由于速度限制，在任意时刻 t，可达位置构成一个区间 [L(t), R(t)]，其中：

• L(t) 是可能到达的最左位置
• R(t) 是可能到达的最右位置

算法过程：

• 初始：时间 0，位置区间为 [0, 0]
• 对于每个流星事件 (tᵢ, xᵢ)：
  1. 让时间从上一个事件推进到 tᵢ，扩展位置区间（考虑速度限制）
  2. 从位置区间中扣除禁止区域 [xᵢ - d, xᵢ + d]
  3. 如果位置区间为空，说明 d 不可行

4. 处理技巧

实际实现时，为了处理连续时间和位置，以及可能的分段区间，需要一些技巧：

• 离散化处理：将连续的区间用关键点表示
• 事件驱动：处理区间合并与分裂
• 精度处理：为避免浮点数误差，常将坐标和时间乘以 2 或 4，用整数运算

复杂度分析

• 排序流星事件：O(n log n)
• 二分答案：O(log (max_distance / ε))，其中 ε 是精度要求
• 每次检查：O(n) 或 O(n log n)，取决于区间操作的实现
• 总复杂度：O(n log n × log(max_distance))，对于 n ≤ 2×10⁵ 是可接受的

算法标签总结

1. 二分答案 - 核心框架
2. 贪心验证 - 按时间顺序处理约束
3. 区间管理 - 维护可达位置集合
4. 运动规划 - 考虑速度限制下的可达性
5. 计算几何（一维） - 处理区间操作

总结

这道题的精髓在于将最大化最小值问题转化为二分答案，然后通过维护随时间演变的可达位置区间来验证可行性。关键在于理解速度限制如何转化为位置区间的扩展，以及流星约束如何转化为位置区间的收缩。这是一个典型的竞赛题目，结合了算法思维和精细的实现技巧。