Link.
Description.
有 \(n\) 个人，第 \(i\) 个人说有 \(a_i\) 个人成绩比他高，有 \(b_i\) 个比他低。
问至少几个人说谎了。
Solution.
首先考虑每个人说的话本质含义是什么。
相当于对他来说，第 \(a_i+1\) 个人到第 \(n-b_i\) 人分数相同。
我们分别设 \(l_i=a_i+1,r_i=n-b_i\)，那也就是所有所选区间要么重合要么互不相连。
然后一个区间最多只能被重合区间长度次。
那么直接把重合区间压缩起来，做一个 dp 即可。
Coding.
点击查看颓怪代码
//是啊，你就是那只鬼了，所以被你碰到以后，就轮到我变成鬼了{{{
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
template<typename T>inline void read(T &x)
{
x=0;char c=getchar(),bz=0;
for(;c<48||c>57;c=getchar()) if(!(c^45)) bz=1;
for(;c>=48&&c<=57;c=getchar()) x=(x<<1)+(x<<3)+(c^48);
bz?x=-x:x;
}/*}}}*/
int n,m,F[100005],N;
struct node{int l,r,v;}a[100005],b[100005];
inline char cmp1(node x,node y) {return x.l^y.l?x.l<y.l:x.r<y.r;}
inline char cmp2(node x,node y) {return x.r^y.r?x.r<y.r:x.l<y.l;}
int main()
{
read(N);for(int i=1;i<=N;i++) read(a[i].l),read(a[i].r),a[i].l++,a[i].r=N-a[i].r;
sort(a+1,a+N+1,cmp1);for(int i=1;i<=N;i++) if(a[i].l<=a[i].r) b[++m]=a[i];
for(int i=1;i<=m;i++)
if(i==1||b[i].l!=b[i-1].l||b[i].r!=b[i-1].r) a[++n]=b[i],a[n].v=1;
else if(a[n].v<a[n].r-a[n].l+1) a[n].v++;
sort(a+1,a+n+1,cmp2),F[1]=a[1].v;
for(int i=2;i<=n;i++)
{
int ls=upper_bound(a+1,a+i,(node){0,a[i].l},cmp2)-a-1;
F[i]=max(F[i-1],F[ls]+a[i].v);
}
return printf("%d\n",N-F[n]),0;
}