专业做网站建设公司深圳互联网公司排行榜
Powered by:NEFU AB-IN
Link
文章目录
- 京东-第2题-撞车
- 题意
- 思路
- 代码
京东-第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] = speedmin_remove = n - len(LIS)
print(min_remove)