把所有人按 $a_i$ 从小到大排序， $a_i$ 越小说明如果那个人说真话，分数越高
对于 $a_i$ 相同的人，如果 $b_i$ 不同那么最多只有一种 $b_i$ 是真的，所以考虑把 $a_i,b_i$ 相同的合并，价值为人数
进一步考虑，对于 $a_i$ 不同的人，他们同时说真话的条件是什么
不妨把这些人看成一个个区间，$a_i,b_i$ 的人所在的区间为 $[a_i+1,n-b_i]$，即在这一个区间的人分数要一样，如果两个不同的区间要同时合法，那么因为他们分数不同，所以两个区间不能有交集
现在题目就转化成了：若干个区间，每个区间有一个价值，取出若干不交的区间使得价值最大
然后按右端点排序，直接 $dp$ 即可
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=2e5+7; int n,m; struct dat { int l,r,v; inline bool operator < (const dat &tmp) const { return l!=tmp.l ? l<tmp.l : r<tmp.r; } inline bool operator != (const dat &tmp) const { return l!=tmp.l||r!=tmp.r; } }c[N],d[N]; int f[N]; inline bool cmp (const dat &A,const dat &B) { return A.r!=B.r ? A.r<B.r : A.l<B.l; } int main() { n=read(); for(int i=1;i<=n;i++) d[i].l=read()+1,d[i].r=n-read(); sort(d+1,d+n+1); int tot=0; for(int i=1;i<=n;i++) if(d[i].l<=d[i].r) c[++tot]=d[i]; int t=n; n=0; for(int i=1;i<=tot;i++) { if(i==1||c[i]!=c[i-1]) d[++n]=c[i],d[n].v=1; else if(d[n].v<d[n].r-d[n].l+1) d[n].v++; } sort(d+1,d+n+1,cmp); for(int i=1,p=1;i<=t;i++) { f[i]=f[i-1]; while(p<=n&&d[p].r==i) { f[i]=max(f[i],f[d[p].l-1]+d[p].v); p++; } } printf("%d ",t-f[t]); return 0; }