记录编号	45937	评测结果	AAAAAAAATA
题目名称	[NOIP 2010冲刺十二]奶牛排队	最终得分	90
用户昵称	苏轼	是否通过	未通过
代码语言	C++	运行时间	1.444 s
提交时间	2012-10-25 22:23:10	内存使用	4.17 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
int n,w[100005],answer;
int main()
{
	freopen ("tahort.in","r",stdin);
	freopen ("tahort.out","w",stdout);
	cin>>n;
	for (int i=1;i<=n;i++)
		cin>>w[i];
	int q[100000][2];
	int tou,wei;
	tou=wei=0;
	q[0][0]=1;
	q[0][1]=n;
	while (tou<=wei)
	{
		int mmin=q[tou][0],mmax=q[tou][0];
		for (int i=q[tou][0];i<=q[tou][1];i++)
		{
			if (w[mmin]>=w[i])
				mmin=i;
			if (w[mmax]<w[i])
				mmax=i;
		}
		if (mmax>mmin)
		{
			if (mmax-mmin+1>answer)
				answer=mmax-mmin+1;
			if (mmin-q[tou][0]+1>answer)
			{
				wei++;
				q[wei][0]=q[tou][0];
				q[wei][1]=mmin;
			}
			if (q[tou][1]-mmax+1>answer)
			{
				wei++;
				q[wei][0]=mmax;
				q[wei][1]=q[tou][1];
			}
		}
		else
		{
			if (mmax-q[tou][0]+1>answer)
			{
				wei++;
				q[wei][0]=q[tou][0];
				q[wei][1]=mmax;
			}
			if (q[tou][1]-mmin+1>answer)
			{
				wei++;
				q[wei][0]=mmin;
				q[wei][1]=q[tou][1];
			}
			if (mmin-mmax-3>answer)
			{
				wei++;
				q[wei][0]=mmax+1;
				q[wei][1]=mmin-1;
			}
		}
		tou++;
	}
	cout<<answer;
	return 0;
}