题解 | 撞车

//要满足题设，我们需要让速度单调递增，不要求严格
//单向道，线性，位置需要升序排序,采用结构体.
//对于速度，我们需要动态规划
//创建一个dp[i],对vi[i]>=dp.back()的尾插,对vi[i]<dp.back()的,upper_bound找到d里严格大于他的一个并替换
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct Drive{
    long long x;
    long long v;
};
bool compare(const Drive a,const Drive b){
    return a.x<b.x;
}
int main(){
    int n;
    cin>>n;
    vector<Drive> d(n);
    for(int i=0;i<n;i++){
        cin>>d[i].x>>d[i].v;
    }
    sort(d.begin(),d.end(),compare);
    vector<long long> vi(n);
    for(int i=0;i<n;i++){
        vi[i]=d[i].v;
    }
    vector<long long> dp;
    dp.push_back(vi[0]);
    for(int i=1;i<n;i++){
        if(vi[i]>=dp.back()){
            dp.push_back(vi[i]);
        }else{
            *upper_bound(dp.begin(),dp.end(),vi[i])=vi[i];
        }
    }
    int len=dp.size();
    cout<<n-len<<"\n";
    return 0;
}