题解 | #撞车#

撞车

https://www.nowcoder.com/practice/d8f779b417094dc1a7864712bb9b4c63

题目链接

撞车

题目描述

一条单向单车道的道路上有 $n$ 辆车，第 $i$ 辆车位于 $p_i$ ，速度大小为 $v_i$ 。为了避免碰撞，可以移除一些车辆。请求出至少需要移除几辆车，才能让剩下的车不发生碰撞。

解题思路

两辆车会发生碰撞的充要条件是：位于后方的车辆速度快于前方的车辆。换言之，要使任意两辆车 $i$ 和 $j$ 不发生碰撞，如果车 $i$ 在车 $j$ 的后方（即 $p_i < p_j$ ），那么必须满足车 $i$ 的速度不大于车 $j$ 的速度（即 $v_i \le v_j$ ）。

这个要求启发我们将问题进行转化：

首先，我们将所有的车辆按照其初始位置 $p_i$ 从小到大进行排序。
排序后，我们就得到了一个按位置排列的车辆序列，以及它们对应的速度序列。
要使这些车辆不发生碰撞，保留下来的车辆（保持它们原有的相对顺序）的速度必须构成一个不下降的序列。

因此，问题就转化成了：对按位置排序后的速度序列，求解其“最长不下降子序列”（LNDS）。这个子序列的长度，就是我们最多可以保留的、不会发生碰撞的车辆数量。

最终，需要移除的车辆数就等于总车辆数 $n$ 减去最长不下降子序列的长度。

求解最长不下降子序列的长度，我们可以复用上一题的思路，即采用贪心算法结合二分查找，在 $\mathcal{O}(n \cdot \log n)$ 的时间复杂度内解决。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Car {
    int p, v;
};

// 自定义排序规则，按位置 p 排序
bool compareCars(const Car& a, const Car& b) {
    return a.p < b.p;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    if (n == 0) {
        cout << 0 << "\n";
        return 0;
    }

    vector<Car> cars(n);
    for (int i = 0; i < n; i++) {
        cin >> cars[i].p >> cars[i].v;
    }

    sort(cars.begin(), cars.end(), compareCars);

    // LNDS 求解过程
    vector<int> d;
    for (int i = 0; i < n; i++) {
        int v = cars[i].v;
        if (d.empty() || v >= d.back()) {
            d.push_back(v);
        } else {
            *upper_bound(d.begin(), d.end(), v) = v;
        }
    }

    cout << n - d.size() << "\n";

    return 0;
}

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

class Car {
    int p, v;

    public Car(int p, int v) {
        this.p = p;
        this.v = v;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        if (n == 0) {
            System.out.println(0);
            return;
        }
        Car[] cars = new Car[n];
        for (int i = 0; i < n; i++) {
            cars[i] = new Car(sc.nextInt(), sc.nextInt());
        }

        // 根据位置 p 排序
        Arrays.sort(cars, Comparator.comparingInt(c -> c.p));

        // LNDS 求解过程
        ArrayList<Integer> d = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int v = cars[i].v;
            if (d.isEmpty() || v >= d.get(d.size() - 1)) {
                d.add(v);
            } else {
                int pos = upperBound(d, v);
                d.set(pos, v);
            }
        }

        System.out.println(n - d.size());
    }

    private static int upperBound(ArrayList<Integer> arr, int key) {
        int low = 0, high = arr.size();
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (arr.get(mid) > key) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }
}

import bisect

n = int(input())
if n == 0:
    print(0)
else:
    cars = []
    for _ in range(n):
        cars.append(list(map(int, input().split())))
    
    # 根据位置 p 排序
    cars.sort(key=lambda x: x[0])
    
    # 提取速度序列
    velocities = [car[1] for car in cars]
    
    # LNDS 求解过程
    d = []
    for v in velocities:
        if not d or v >= d[-1]:
            d.append(v)
        else:
            # 找到 d 中第一个大于 v 的元素的位置并替换
            pos = bisect.bisect_right(d, v)
            d[pos] = v
            
    print(n - len(d))