题解 | 撞车

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

struct car{
    int x,v;
};
bool compare(const car&a,const car&b){
    return a.x<b.x;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<car>a(n);
    for(int i=0;i<n;i++){
        cin>>a[i].x>>a[i].v;
    }
    sort(a.begin(),a.end(),compare);
    vector<int>lis;
    for(car c:a){
        auto it=upper_bound(lis.begin(),lis.end(),c.v);
        if(it==lis.end())lis.push_back(c.v);
        else *it=c.v;
    }
    cout<<n-lis.size();
    return 0;
}