Description：

一次考试共有 $n$ 个人参加，第 $i$ 个人说：“有 $a_i$ 个人分数比我高， $b_i$ 个人分数比我低。”问最少有几个人没有说真话(可能有相同的分数)。 $1\le n \le 100000$

Solution：

先把发言相同的人合并并把个数存下来，发现按照这些人的说法 $[a_i+1,n - b_i]$ 这些人的分数应该相同且与其他人分数不同，于是变成了在数轴上有很多带权的线段，可以选很多线段并获得他们的权值和，线段不能重叠，因为不能有一个人有两个分数，于是 $DP$ 一下即可。注意权值不能超过线段长度。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

#define MAXN 100010

struct ex{int a,b;}p[MAXN];

bool cmp(ex x,ex y){return (x.b == y.b ? x.a < y.a : x.b < y.b);}

struct line{int l,r,v;}e[MAXN];

bool cmp_e(line x,line y){return x.r < y.r;}

int cnt = 0;

int f[MAXN];

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d%d",&p[i].a,&p[i].b);

	sort(p + 1,p + 1 + n,cmp);

	for(int i = 1;i <= n;++i)

		if(p[i].a == p[i - 1].a && p[i].b == p[i - 1].b)e[cnt].v += 1;

		else{e[++cnt].v = 1;e[cnt].l = p[i].a + 1;e[cnt].r = n - p[i].b;}

	sort(e + 1,e + 1 + cnt,cmp_e);

	for(int i = 1;i <= cnt;++i)if(e[i].v > e[i].r - e[i].l + 1)e[i].v = e[i].r - e[i].l + 1;

	for(int i = 1,j = 1;i <= n && j <= cnt;++i)

	{

		f[i] = f[i - 1];

		for(;e[j].r == i;++j)f[i] = max(f[i],f[e[j].l - 1] + e[j].v);

	}

	cout << n - f[n] << endl;

	return 0;

}