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

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

代码

java

import java.util.*;

题目内容

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

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

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

输入描述

第一行一个整数 $n(1 ≤n≤ 10^5)$，表示车的数量。

接下来$n$ 行，每行两个整数 $x_i,v_i(|x_i|,|v_i|,|v_i|≤ 10^9)$，表示车的位置和速度的大小。

数据保证 $x_i$ 互不相同。

输出描述

输出一行一个整数，表示需要移除车的数量。

样例1

输入

3
-1 -1
0 0
1 1

输出

0

说明

样例2

输入

3
-1 1
0 0
1 -1

输出

2

说明