记录编号	547110	评测结果	AAAAAAAAAAA
题目名称	[USACO Feb08] 麻烦的聚餐	最终得分	100
用户昵称	leon	是否通过	通过
代码语言	C++	运行时间	0.018 s
提交时间	2019-11-20 20:54:33	内存使用	14.23 MiB

#include<bits/stdc++.h>
using namespace std;
int n,a[50100],b[50010],c[50010],tot=1,s=999999999;
const int inf=999999999;
int main(){
    freopen("egroup.in","r",stdin);
    freopen("egroup.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++){
    	cin>>a[i];
    }
    b[1]=a[1];
	for(int i=2;i<=n;i++){
	if(a[i]>=b[tot])b[++tot]=a[i];
	else
	b[upper_bound(b+1,b+1+tot,a[i])-b]=a[i];
	}
	s=n-tot;
	tot=1;
	for(int i=1;i<=n;i++){
		a[i]=-a[i];
	}
	c[1]=a[1];
	for(int i=2;i<=n;i++){
	if(a[i]>=c[tot])c[++tot]=a[i];
	else
	c[upper_bound(c+1,c+tot+1,a[i])-c]=a[i];
	}
	s=min(n-tot,s);
	cout<<s;
    	return 0;
    }