http://www.lydsy.com/JudgeOnline/problem.php?id=2298

题意

n个人，每个人说Xi个人比我低，Yi个人比我高

问最少有多少个人说假话

题解

其实想的和题解一样，但是忽略题解中所说的情况，一直wa，

掉（xi + yi ≥ n）的，

每句话都可以表示成一个[yi + 1, n - xi]的区间。

一开始所有的区间权值为1；

然后把同样的区间合并，权值设为合并在一起的区间数量

选出最多的互补相交的区间，记为k

那么答案就是n-k。

需要注意的是如果某个同样区间的数量>区间长度，要改成区间长度

#include<cstdio>
#include<algorithm>
#include<vector>
#define MP make_pair
#define PB push_back
#define s first
#define t second
using namespace std;
typedef pair<int,int> pr;
int n,f[100001],tot;
vector<pr> p;

bool cmp(pr a,pr b)
{
	if(a.t!=b.t) return a.t<b.t;
	else return a.s<b.s;
}
int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		int x,y;scanf("%d%d",&x,&y);
		if(x+y>=n)	continue;
		p.PB(MP(y+1,n-x));tot++;
	}
	sort(p.begin(),p.end(),cmp);
	int j=0;
	for(int i=1;i<=n;i++)
	{
		f[i]=f[i-1];
		while(j<tot && p[j].t==i)
		{
			int k;for(k=j;k<tot && p[k]==p[j];k++);
			f[i]=max(f[i],f[p[j].s]+min(k-j,p[j].t-p[j].s));
			j=k;
		}
	}
	printf("%d\n",n-f[n]);
}