题解 | #撞车#

分析

因为是单行道, 不发生碰撞的条件是并且

那么只需要将车按照位置排序, 然后计算最长不下降子序列即可

因为, 需要贪心 + 二分优化计算

代码实现

#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 1e5 + 10, MOD = 998244353;

int n;
struct F {
    int x, v;

    bool operator< (const F f) const {
        return x < f.x;
    }
} w[N];

LL f[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int x, v;
        cin >> x >> v;
        w[i] = {x, v};
    }

    sort(w + 1, w + n + 1);

    int len = 0;
    for (int i = 1; i <= n; ++i) {
        int l = 0, r = len;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (f[mid] <= w[i].v) l = mid;
            else r = mid - 1;
        }
        len = max(len, l + 1);
        f[l + 1] = w[i].v;
    }

    cout << n - len << '\n';
    return 0;
}