技术问询：计算首个车手抵达指定位置前的赛车超车次数

DevOps 小满

2026-7-6

问题：超车次数计算实现正确性验证

给定长度为N的racers数组，每个车手拥有speed（取值范围1 ≤ speed[i] ≤ 10^8）和起始位置，数组按起始位置升序排列（1 ≤ positions[0] < positions[1] < … < positions[n] < 10^9）。车手们在无限长赛道上同向（从左至右）行驶，需要计算首个车手到达指定position（满足racers[0].Position < position < racers[n].Position）前发生的超车次数。超车的定义是：当车手A的位置等于车手B的位置时（仅当A初始位置小于B但速度大于B时发生）。

用户给出的实现代码如下：

static uint OvertakingCountAtPosition(Racer[] racers, double position, uint racerCount)
{
    var overtakingCount = 0u;

    for (int i = 0; i < racerCount; i++)
    {
        var time1 = (position - racers[i].Position) / racers[i].Speed;
        for (int j = i + 1; j < racerCount; j++)
        {
            var time2 = (position - racers[j].Position) / racers[j].Speed;
            if (0.0001d >= time1 - time2)
            {
               overtakingCount++;
            }
        }
    }

    return overtakingCount;
}

用户的核心逻辑：选取一名车手，计算其到目标位置的时间；遍历其前方车手，对比时间，若前方车手耗时≥该车手则判定超车。用户想知道这个实现是否正确，同时提到认为存在更优解法，但当前先寻求可行方案。

回答

你的实现核心逻辑方向是对的，但存在几个问题需要修正，才能保证正确性：

浮点数精度问题
你用0.0001d >= time1 - time2来判断time1 <= time2，但这个误差阈值是主观设定的，可能会导致两种错误：
- 实际time1略小于time2，但因为浮点数计算误差被误判为相等，多统计了超车次数；
- 实际time1刚好等于time2（即两车在目标位置同时到达），但因为误差被漏掉统计。
  更严谨的做法是把除法转换成乘法来比较，完全避免浮点数误差：
  原条件(position - pos_i)/speed_i <= (position - pos_j)/speed_j，因为speed_i和speed_j都是正数，交叉相乘后不等号方向不变，得到：
  (position - pos_i) * speed_j <= (position - pos_j) * speed_i
  用整数运算执行这个判断，结果会更准确。
边界情况处理
题目要求统计的是首个车手到达目标位置前的超车次数，也就是说，如果两车刚好在目标位置同时到达，这种情况不算超车（因为是在到达时刻才相遇，不是到达之前）。所以你的条件应该是time1 < time2（或者转换成乘法后的(position - pos_i)*speed_j < (position - pos_j)*speed_i），而不是<=。
无效统计的过滤
根据超车定义，只有当初始位置i < j（即i在j左边）且speed_i > speed_j时，才有可能发生超车。如果speed_i <= speed_j，不管时间如何，i都不可能超过j，这部分可以直接跳过统计，减少不必要的计算。

修正后的核心判断逻辑示例：

if (racers[i].Speed > racers[j].Speed)
{
    // 用乘法避免浮点数误差，判断i到达目标的时间是否小于j（即i能在到达目标前超过j）
    long left = (long)(position - racers[i].Position) * racers[j].Speed;
    long right = (long)(position - racers[j].Position) * racers[i].Speed;
    if (left < right)
    {
        overtakingCount++;
    }
}

另外，你的实现时间复杂度是O(n²)，对于n较大的情况效率很低，更优解法可以用归并排序的思路统计符合条件的逆序对（把问题转化为统计满足speed_i > speed_j且(position - pos_i)/speed_i < (position - pos_j)/speed_j的(i,j)对数量），时间复杂度可以降到O(n log n)，不过这是优化方向，当前先保证正确性的话，先修正上面的问题即可。

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