题目
题解
求最多说真话的人数，答案即为n-ans
设dp[i]表示在前i名中最多有多少人说真话
dp[i] = max{dp[j-1]+sum[j][i]} 其中sum[j][i]表示名次区间为[j, i]的人数

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
const int N=100002;
int f[N],a,b,l,r,i,j,n;
map<pair<int,int>,int>s;
vector<int>q[N];
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline int read(){
    int x=0,fl=1;char ch=gc();
    for (;ch<48||ch>57;ch=gc())if(ch=='-')fl=-1;
    for (;48<=ch&&ch<=57;ch=gc())x=(x<<3)+(x<<1)+(ch^48);
    return x*fl;
}
int main(){
    n=read();
    for (i=1;i<=n;i++){
        a=read();b=read();
        l=a+1;r=n-b;
        if (l>r) continue;
        if (!(s[mp(l,r)]++)) q[r].push_back(l);
    }
    for (i=1;i<=n;i++){
        f[i]=f[i-1];
        for (j=0;j<q[i].size();j++) f[i]=max(f[i],f[q[i][j]-1]+min(i-q[i][j]+1,s[mp(q[i][j],i)]));
    }
    printf("%d",n-f[n]);
}