【BZOJ2298】【HAOI2011】problem a

  很显然一个DP，一个人有\(a_i\)个人分数比他高，\(b_i\)个人分数比他低，那么这个人对应的名次区间就是\([b_i + 1 , n - a_i]\)，最多的说真话的人数就是能选出最多的不相交的（或者相等的）名次区间。一个名次区间\([a , b]\)最多有\(b-a+1\)个人说真话。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=100010;

struct Edge {int u,v;}E[maxn];
bool cmp(const Edge &a,const Edge &b) {return a.u<b.u || a.u==b.u && a.v<b.v;}

int f[maxn];
int n,Ecnt;

int main()
{
	scanf("%d",&n);
	for (int i=1,x,y;i<=n;i++) 
	{
		scanf("%d%d",&x,&y);
		if (x+y>=n) continue;
		Ecnt++;
		E[Ecnt].u=n-x;
		E[Ecnt].v=y;
	}
	sort(E+1,E+1+Ecnt,cmp);
	for (int i=1,j=1;i<=n;i++)
	{
		while (j<=Ecnt && E[j].u==i)
		{
			int cnt=1;
			while (j<Ecnt && E[j+1].u==i && E[j+1].v==E[j].v) cnt++,j++;
			f[i]=max(f[i],f[E[j].v]+min(cnt,E[j].u-E[j].v));
			j++;
		}
		f[i]=max(f[i],f[i-1]);
	}
	printf("%d\n",n-f[n]);
	return 0;
}