分析
每个人的话相当于 $[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;
}