记录编号	431750	评测结果	AAAAAAAAAA
题目名称	[HAOI 2011]问题A	最终得分	100
用户昵称	CSU_Turkey	是否通过	通过
代码语言	C++	运行时间	0.395 s
提交时间	2017-08-01 18:18:53	内存使用	4.13 MiB

#include<bits/stdc++.h>
using namespace std;
int n,f[100005];
struct t
{
	int l,r,cost;
	bool operator < (const t &b)const{
		return l<b.l;
	}
}e[100005];
map<int,int>s[100005];
int main()
{
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
//	freopen("1.txt","r",stdin);
	scanf("%d",&n);
	int h=0;
	for(int i=1;i<=n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		x++;
		y=n-y;
		if(s[x].find(y)==s[x].end())
		{
			e[++h].cost=1;
			e[h].l=x;
			e[h].r=y;
			s[x][y]=h;
		}
		else
		{
			e[s[x][y]].cost++;
		}
	}
	for(int i=1;i<=h;i++)
	{
		e[i].cost=min(e[i].cost,e[i].r-e[i].l+1);
		e[i].cost=max(e[i].cost,0);
	}
	sort(e+1,e+h+1);
	int o=1;
	for(int i=1;i<=n;i++)
	{
		f[i]=max(f[i-1],f[i]);
		while(e[o].l==i)
		{
			f[e[o].r]=max(f[e[o].r],f[i-1]+e[o].cost);
			o++;
		}
	}
//	for(int i=1;i<=n;i++)cout<<f[i]<<" ";
	cout<<n-f[n];
	return 0;
}