题目内容

一条单向单车道的道路上有$n$辆车，第$i$辆车位于 $x_i$;，速度大小为 $v_i$ 。

显然，如果车辆保持此速度行驶下去，在大多数情况下都会发生碰撞。

现在小塔想知道，至少需要移除几辆车，才能让这些车不发生碰撞?

输入描述

思路: 动态规划 + 二分查找

首先将所有车辆按位置升序排序，确保处理顺序正确。然后提取速度序列，目标是找到最长不下降子序列，代表可以保留的最大车辆数而不发生碰撞。使用动态规划和二分查找的方法高效计算最长不下降子序列。最后，最少需要移除的车辆数即为总车辆数减去最长不下降子序列大小，从而避免所有可能的碰撞。

代码

java

import java.util.*;