撞车

[题目链接](https://www.nowcoder.com/practice/d8f779b417094dc1a7864712bb9b4c63)

思路

一条单向单车道上有 $n$ 辆车，第 $i$ 辆车位于 $x_i$ ，速度为 $v_i$ 。求至少移除几辆车，才能使剩余车辆不发生碰撞。

碰撞条件分析

考虑两辆车 $A$ （位置 $x_A$ ）和 $B$ （位置 $x_B$ ），其中 $x_A < x_B$ 。在时刻 $t$ 它们的位置分别为 $x_A + v_A t$ 和 $x_B + v_B t$ 。碰撞发生当且仅当存在 $t > 0$ 使得：

$ $x_A + v_A t = x_B + v_B t$ $

解得 $t = \frac{x_B - x_A}{v_A - v_B}$ 。由于 $x_B - x_A > 0$ ，所以 $t > 0$ 当且仅当 $v_A > v_B$ ，即后车速度大于前车速度。

转化为最长非递减子序列

因此，要使所有剩余车辆不发生碰撞，按位置排序后，速度必须非递减。这等价于：

将所有车按位置 $x$ 从小到大排序；
在速度序列上求最长非递减子序列（LNDS）的长度 $L$ ；
答案为 $n - L$ 。

求 LNDS

最长非递减子序列可以用与 LIS 类似的 $O(n \log n)$ 贪心 + 二分方法求解。维护一个数组 $\textit{tails}$ ，其中 $\textit{tails}[i]$ 表示长度为 $i+1$ 的非递减子序列的最小末尾值。对于每个速度 $v$ ：

用 upper_bound 找到 $\textit{tails}$ 中第一个严格大于 $v$ 的位置；
若不存在，说明 $v$ 可以接在最长子序列后面，将 $v$ 追加到 $\textit{tails}$ ；
否则，用 $v$ 替换该位置的值。

样例验证

示例 1：位置 $-1, 0, 1$ ，速度 $-1, 0, 1$ 。按位置排序后速度为 $[-1, 0, 1]$ ，已非递减，LNDS = 3，答案为 $3 - 3 = 0$ 。

示例 2：位置 $-1, 0, 1$ ，速度 $1, 0, -1$ 。按位置排序后速度为 $[1, 0, -1]$ ，LNDS = 1，答案为 $3 - 1 = 2$ 。

复杂度分析

时间复杂度： $O(n \log n)$ ，排序 $O(n \log n)$ 加上二分求 LNDS $O(n \log n)$ 。
空间复杂度： $O(n)$ 。

代码

C++
Java

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    vector<pair<int,int>> cars(n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &cars[i].first, &cars[i].second);
    }
    sort(cars.begin(), cars.end());
    vector<int> tails;
    for (int i = 0; i < n; i++) {
        int v = cars[i].second;
        auto it = upper_bound(tails.begin(), tails.end(), v);
        if (it == tails.end()) {
            tails.push_back(v);
        } else {
            *it = v;
        }
    }
    printf("%d\n", n - (int)tails.size());
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        int[][] cars = new int[n][2];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            cars[i][0] = Integer.parseInt(st.nextToken());
            cars[i][1] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(cars, (a, b) -> a[0] - b[0]);
        ArrayList<Integer> tails = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int v = cars[i][1];
            int lo = 0, hi = tails.size();
            while (lo < hi) {
                int mid = (lo + hi) / 2;
                if (tails.get(mid) > v) hi = mid;
                else lo = mid + 1;
            }
            if (lo == tails.size()) tails.add(v);
            else tails.set(lo, v);
        }
        System.out.println(n - tails.size());
    }
}