「HAOI 2011」problem a

题目大意：一次考试共有 $n$ 个人参加，第 $i$ 个人说：“有 $a_i$ 个人分数比我高，$b_i$ 个人分数比我低。”问最少有几个人没有说真话（可能有相同的分数）。$1≤n≤100000，0≤a_i,b_i≤n$

转换成线段覆盖问题，注意判断 $a_i+b_i<n$，以及完全相同的线段的情况。

// luogu-judger-enable-o2
#include <cstdio>
#include <algorithm>

const int N = 100005;

struct Node {
    int l, r;
    bool operator < (const Node &rhs) const {
        if (r == rhs.r) return l < rhs.l;
        return r < rhs.r;
    }
} a[N];

int mx[N], w[N];

int read() {
    int x = 0; char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return x;
}
int max(int x, int y) {
    return x > y ? x : y;
}

int main() {
    int n = read(), m = 0, ans = 0;
    for (int i = 1; i <= n; ++i) {
        int x = read(), y = read();
        if (x + y < n) a[++m].l = x + 1, a[m].r = n - y;
    }
    std::sort(a + 1, a + m + 1);
    for (int i = 1, j = 1; i <= m; ++i) {
        if (a[i].l != a[i-1].l || a[i].r != a[i-1].r) j = i;
        w[j] += w[j] == a[i].r - a[i].l + 1 ? 0 : 1;
    }
    for (int i = 1, j = 1; i <= m; ++i) {
        int tmp = mx[j-1];
        for (; j <= a[i].r; ++j) mx[j] = tmp;
        mx[a[i].r] = max(mx[a[i].r], mx[a[i].l-1] + w[i]);
        ans = max(ans, mx[a[i].r]);
    }
    printf("%d\n", n - ans);
    return 0;
}

时间复杂度 $O(n \log n)$