Luogu

分析

每个人的话相当于 $[a_i+1,n-b_i]$ 中的人排名相同。

那么如果两个人的话不同且对应的区间无交，他们就可能都说了真话。

把相同的区间缩在一起，问题变成每个区间有一个权值，选出若干个无交的区间使得权值和最大。

这个可以直接 DP，把所有区间按右端点排序后，二分找到最后的左端点小于当前右端点的位置，然后转移即可。

注意把 $a_i+1>n-b_i$ 的人掉，这些人一定说了假话；还要注意如果有多个人的区间都是 $[l,r]$，那么只有至多 $r-l+1$ 个人说了真话。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,m,dp[N];
struct node { int l,r,w; } a[N],b[N];
bool operator !=(node a,node b) { return a.l!=b.l||a.r!=b.r; }

int main() {
    n=read();
    for (int i=1;i<=n;++i) a[i]={read()+1,n-read(),1};
    sort(a+1,a+n+1,[](node a,node b) {
        return a.l!=b.l?a.l<b.l:a.r<b.r;
    });
    for (int i=1;i<=n;++i) {
        if (a[i].l>a[i].r) continue;
        if (a[i]!=a[i-1]) b[++m]=a[i];
        else ++b[m].w;
    }
    for (int i=1;i<=m;++i) b[i].w=min(b[i].w,b[i].r-b[i].l+1);
    sort(b+1,b+m+1,[](node a,node b) {
        return a.r!=b.r?a.r<b.r:a.l<b.l;
    });
    for (int i=1;i<=m;++i) {
        int L=1,R=i-1;
        while (L<R) {
            int mid=(L+R+1)>>1;
            if (b[mid].r<b[i].l) L=mid;
            else R=mid-1;
        }
        dp[i]=max(dp[i-1],dp[L]+b[i].w);
    }
    int ans=0;
    for (int i=1;i<=m;++i) ans=max(ans,dp[i]);
    printf("%d\n",n-ans);
    return 0;
}