京东-第2题-撞车

Powered by:NEFU AB-IN

Link

京东-第2题-撞车

题意

一条单向单车道的道路上有n辆车，第i辆车位于 xi;，速度大小为 vi。
显然，如果车辆保持此速度行驶下去，在大多数情况下都会发生碰撞。
现在小塔想知道，至少需要移除几辆车，才能让这些车不发生碰撞

思路

将所有车辆按位置升序排序，提取速度，找最长递增子序列（LIS）即可。最少需要移除的车辆数即为总车辆数减去LIS长度。

代码

n, = IO.read()
cars = []
for _ in range(n):
    xi, vi = IO.read()
    cars.append((xi, vi))

cars.sort(key=lambda x: x[0])

speeds = [vi for xi, vi in cars]

LIS = []
for speed in speeds:
    pos = bisect.bisect_left(LIS, speed)
    if pos == len(LIS):
        LIS.append(speed)
    else:
        LIS[pos] = speed

min_remove = n - len(LIS)
print(min_remove)