做网站被用作非法用途,网站建设丶金手指花总11,海门市规划建设局网站,福田网站制作哪家好Powered by:NEFU AB-IN
Link 文章目录 京东-第2题-撞车题意思路代码 京东-第2题-撞车
题意
一条单向单车道的道路上有n辆车#xff0c;第i辆车位于 xi;#xff0c;速度大小为 vi。 显然#xff0c;如果车辆保持此速度行驶下去#xff0c;在大多数情况下都会发生碰撞。 现…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(keylambda 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)
