不同速度与起点的喷气式滑艇领先者判定算法设计及优化问询

问题描述 #

现有n艘喷气式滑艇沿平行方向竞速，每艘滑艇i拥有恒定速度vᵢ，t=0时刻位于位置pᵢ。定义领先为滑艇位置处于所有其他滑艇右侧。需设计算法计算所有曾在某一时刻处于领先位置的滑艇集合。

已知条件：所有pᵢ、vᵢ均不相同，且无三艘滑艇同时处于同一位置。

示例：3艘滑艇速度分别为1、2、3，初始位置为10、0、-1，算法需返回滑艇1（t=0时领先）和滑艇3（t≥5.5时领先），滑艇2从未领先。

算法思路 #

通过分析每艘滑艇成为领先者的时间约束，直接判断该滑艇是否曾领先，具体步骤如下：

1. 初始化空集合result，用于存放所有曾领先的滑艇。
2. 对每艘滑艇i，执行以下操作：
   • 计算领先的时间下界：遍历所有速度小于vᵢ的滑艇j，计算i超过j的时间t_low_ij = max(0, (pⱼ - pᵢ)/(vᵢ - vⱼ))（仅保留非负时间，因为t<0为过去时刻，不计入）。取所有t_low_ij的最大值作为t_low（若没有速度小于vᵢ的滑艇，t_low设为0）。
   • 计算领先的时间上界：遍历所有速度大于vᵢ的滑艇j，计算j超过i的时间t_high_ij = (pᵢ - pⱼ)/(vⱼ - vᵢ)。若t_high_ij < 0则忽略（因为t≥0时该约束自动满足），取剩余t_high_ij的最小值作为t_high（若没有速度大于vᵢ的滑艇，t_high设为+∞）。
   • 判断是否曾领先：若t_low < t_high，说明存在t ∈ [t_low, t_high)使得滑艇i成为领先者，将i加入result。
3. 返回result集合。

正确性证明 #

1. 约束合理性：
   • 对于速度小于i的滑艇j，t_low_ij是i超过j的最早非负时间，当t ≥ t_low_ij时，i的位置始终严格大于j的位置（因vᵢ>vⱼ，且无三艇同位置）。
   • 对于速度大于i的滑艇j，t_high_ij是j超过i的时间，当t < t_high_ij时，i的位置始终严格大于j的位置。
2. 有效时间区间的意义：
   当t_low < t_high时，区间[t_low, t_high)内的所有时刻，滑艇i的位置均大于其他所有滑艇的位置，即i处于领先状态。反之，若t_low ≥ t_high，则不存在任何t≥0使得i满足所有领先约束，即i从未领先。
3. 无遗漏无错误：
   遍历所有滑艇并逐一判断，确保所有曾领先的滑艇被加入集合，从未领先的滑艇被排除，完全符合问题要求。

时间复杂度分析 #

• 算法需遍历n艘滑艇，每艘滑艇需与其他n-1艘滑艇进行比较计算，总操作数为O(n²)。
• 过程中仅涉及基础算术运算和最值查找，无更高阶的操作（如排序），因此时间复杂度为O(n²)，目前尚未发现时间复杂度优于O(n²)的解法。

内容的提问来源于stack exchange，提问作者ricolxwz