题解 | 撞车

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

struct car{
    int x, v;
};
int main() {
    int n;
    cin >> n;
    vector<car> s(n);
    for (int i = 0; i < n; i++) {
        cin >> s[i].x >> s[i].v;
    }
    sort(s.begin(), s.end(), [](const car a, const car b){
        return a.x < b.x;
    }); // 对车的位置进行排序
    // 求出车序列的最长非递减子序列

    vector<int> len;
    len.push_back(s[0].v);
    for (int i = 1; i < n; i++) {
        if (s[i].v >= len.back()) {
            len.push_back(s[i].v);
        }
        else {
            *upper_bound(len.begin(), len.end(), s[i].v) = s[i].v;
        }
    }
    cout << n - len.size();
}