记录编号	160986	评测结果	AAAAAAAAAAA
题目名称	139.[USACO Feb08] 麻烦的聚餐	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	0.007 s
提交时间	2015-04-30 13:10:57	内存使用	1.05 MiB

#include <cstdio>
#include <cstring>
 
using namespace std;
 
int data[50000],datar[50000],n,ans[50000],ansr[50000],len,lenr;
 
int MIN(int a,int b)
{return a>b? b:a;}
 
int bs(int dt)
{
    int l=1,r=len,m;
    while(l<r)
    {
        m=l+(r-l)/2;
        if(ans[m]>dt) r=m;
        else l=m+1;
    }
    return l;
}
int bsr(int dt)
{
    int l=1,r=lenr,m;
    while(l<r)
    {
        m=l+(r-l)/2;
        if(ansr[m]>dt) r=m;
        else l=m+1;
    }
    return l;
}
int main()
{
freopen("egroup.in","r",stdin);
freopen("egroup.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {scanf("%d",&data[i]);datar[n-i+1]=data[i];}
    ans[1]=data[1];len=1;
    for(int i=2;i<=n;i++)
    {
        if(ans[len]<=data[i])
            ans[++len]=data[i];
        else
            ans[bs(data[i])]=data[i];
    }
    ansr[1]=datar[1];lenr=1;
    for(int i=2;i<=n;i++)
    {
        if(ansr[lenr]<=datar[i])
            ansr[++lenr]=datar[i];
        else
            ansr[bsr(datar[i])]=datar[i];
    }
    printf("%d",MIN(n-len,n-lenr));
    return 0;
}