记录编号	79066	评测结果	AAAAAAAAAAA
题目名称	[USACO Feb08] 麻烦的聚餐	最终得分	100
用户昵称	zjmfrank2012	是否通过	通过
代码语言	C++	运行时间	0.011 s
提交时间	2013-11-05 00:20:46	内存使用	0.77 MiB

#include<fstream>
using namespace std;
ifstream fi("egroup.in");
ofstream fo("egroup.out");
int n,a[30001]={0},d[30001]={0},a1[30001]={0},d1[30001]={0};
int find(int x,int l,int r)
{
	if(l==r)
	{
		return r;
	}
    int m=(l+r)/2;
	if(x>=d[m])
	{
		return find(x,m+1,r);
	}
	if(x<d[m])
	{
		return find(x,l,m);
	}
}
int find1(int x,int l,int r)
{
	if(l==r)
	{
		return r;
	}
    int m=(l+r)/2;
	if(x>=d1[m])
	{
		return find1(x,m+1,r);
	}
	if(x<d1[m])
	{
		return find1(x,l,m);
	}
}
int main()
{
	int ans,i,t,ans1;
	fi>>n;
	for(i=1;i<=n;i++)
	{
		fi>>a[i];
		a1[n-i+1]=a[i];
		d[i]=999999;
		d1[i]=999999;
	}
	d[1]=a[1];
	ans=1;
	for(i=2;i<=n;i++)  
	{  
		t=find(a[i],1,n);
        d[t]=min(a[i],d[t]);
		ans=max(ans,t);
	}  
	d1[1]=a1[1];
	ans1=1;
	for(i=2;i<=n;i++)  
	{  
		t=find1(a1[i],1,n);
        d1[t]=min(a1[i],d1[t]);
		ans1=max(ans1,t);
	}
	fo<<n-max(ans,ans1);
	return 0;
}