撞车

思路

题目在说什么？数轴上有 $n$ 辆车，第 $i$ 辆车位于 $p_i$ ，速度为 $v_i$ 。时刻 $t$ 时第 $i$ 辆车在 $p_i + v_i \cdot t$ 。如果存在 $t > 0$ 使得两辆车在同一位置，就会撞车。问最少移除多少辆车才能让剩下的车互不碰撞。

先把所有车按位置从小到大排序。考虑排序后相邻的两辆车 $i < j$ （即 $p_i < p_j$ ），它们碰撞的条件是什么？

碰撞时刻 $t = \frac{p_j - p_i}{v_i - v_j}$ ，要求 $t > 0$ 。因为 $p_j - p_i > 0$ ，所以需要 $v_i > v_j$ ，也就是后面的车速度比前面的车慢，前面的车会被追上。

反过来，如果 $v_i \le v_j$ ，这两辆车永远不会碰撞（速度相等时因为位置不同也不会碰）。

推广到任意两辆车（不只是相邻的），结论一样：排序后，两辆车不碰撞当且仅当速度是非递减的。

所以问题就变成了：排序后，从速度序列中找一个最长非递减子序列，剩下的车都要移除。答案就是 $n$ 减去这个最长非递减子序列的长度。

最长非递减子序列和 LIS（最长严格递增子序列）的做法几乎一样，只需要把二分查找中的 lower_bound 换成 upper_bound 即可，时间复杂度 $O(n \log n)$ 。

代码

C++
Java
Python3
JavaScript

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<pair<long long,long long>> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i].first >> a[i].second;
    }
    sort(a.begin(), a.end());
    // 最长非递减子序列
    vector<long long> tails;
    for(int i = 0; i < n; i++){
        long long v = a[i].second;
        auto it = upper_bound(tails.begin(), tails.end(), v);
        if(it == tails.end()){
            tails.push_back(v);
        } else {
            *it = v;
        }
    }
    cout << n - (int)tails.size() << endl;
    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());
        long[][] a = new long[n][2];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            a[i][0] = Long.parseLong(st.nextToken());
            a[i][1] = Long.parseLong(st.nextToken());
        }
        Arrays.sort(a, (x, y) -> Long.compare(x[0], y[0]));
        // 最长非递减子序列
        List<Long> tails = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            long v = a[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());
    }
}

import bisect, sys
input = sys.stdin.readline

def main():
    n = int(input())
    a = []
    for _ in range(n):
        p, v = map(int, input().split())
        a.append((p, v))
    a.sort()
    tails = []
    for _, v in a:
        pos = bisect.bisect_right(tails, v)
        if pos == len(tails):
            tails.append(v)
        else:
            tails[pos] = v
    print(n - len(tails))

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', l => lines.push(l));
rl.on('close', () => {
    const n = parseInt(lines[0]);
    const a = [];
    for (let i = 1; i <= n; i++) {
        const [p, v] = lines[i].split(' ').map(Number);
        a.push([p, v]);
    }
    a.sort((x, y) => x[0] - y[0]);
    const tails = [];
    for (let i = 0; i < n; i++) {
        const v = a[i][1];
        let lo = 0, hi = tails.length;
        while (lo < hi) {
            const mid = (lo + hi) >>> 1;
            if (tails[mid] > v) hi = mid;
            else lo = mid + 1;
        }
        if (lo === tails.length) tails.push(v);
        else tails[lo] = v;
    }
    console.log(n - tails.length);
});

复杂度

时间复杂度： $O(n \log n)$ ，排序 $O(n \log n)$ ，求最长非递减子序列 $O(n \log n)$ 。
空间复杂度： $O(n)$ 。

题解 | #撞车#

撞车

思路

代码

复杂度