题解 | 撞车

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
    int n;
    cin >> n;
    vector<ll> x(n),v(n);
    unordered_map<int,int> hx(n);
    for(int i=0; i<n; i++){
        cin >> x[i] >> v[i];
        hx[x[i]] = v[i];
    }
    vector<int> dp;
    sort(x.begin(),x.end());
    for(int i=0; i<n; i++){
        if(dp.empty() || hx[x[i]] >= dp.back()){
            dp.push_back(hx[x[i]]);
        }else {
            *upper_bound(dp.begin(),dp.end(), hx[x[i]]) = hx[x[i]];
        }
    }
    cout << n-dp.size();
}