题解 | 撞车

//豆包批注
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

bool cmp(const pair<ll, ll>& a, const pair<ll, ll>& b) {
    return a.first < b.first; // 按位置升序排序
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    if (n == 0) {
        cout << 0 << '\n';
        return 0;
    }
    
    vector<pair<ll, ll>> cars(n);
    for (int i = 0; i < n; i++) {
        cin >> cars[i].first >> cars[i].second;
    }
    
    // 按位置排序
    sort(cars.begin(), cars.end(), cmp);
    
    // 提取速度
    vector<ll> v;
    for (int i = 0; i < n; i++) {
        v.push_back(cars[i].second);
    }
    
    // 使用贪心+二分求最长非递减子序列长度
    vector<ll> d;
    d.push_back(v[0]);
    
    for (int i = 1; i < n; i++) {
        if (v[i] >= d.back()) {
            d.push_back(v[i]);
        } else {
            // 找到d中第一个大于v[i]的元素并替换
            *upper_bound(d.begin(), d.end(), v[i]) = v[i];
        }
    }
    
    // 最少需要移除的车辆数 = 总车辆数 - 最长非递减子序列长度
    cout << n - d.size() << '\n';
    
    return 0;
}