比赛 20120419s 评测结果 AAWAAAAAAA
题目名称 河床 最终得分 90
用户昵称 feng 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2012-04-19 09:50:08
显示代码纯文本
#include<fstream>
using namespace std;
int deep[30001];
int f[30001];
int queue[30001];
int n,m,i,j,k,p,x,y;
int maxn,minn;
int qhead,dhead,tail;
int main()
{
	ifstream fin("riverbed.in");
	ofstream fout("riverbed.out");
	fin>>n>>k;
	for (i=1;i<=n;i++)
	{
		fin>>deep[i];
		queue[i]=deep[i];
	}
	dhead=1;
	qhead=1;
	maxn=0;
	minn=100000;
	x=0;
	for (tail=1;tail<=n;tail++)
	{
		if (deep[dhead]>=deep[tail]) {dhead=tail;}
		if (deep[qhead]<=deep[tail]) {qhead=tail;}
		if (deep[qhead]-deep[dhead]>k)
		{
			if (qhead<dhead)
			{
				y=qhead;
				for (i=x+1;i<=y;i++)
					f[i]=tail-i;
				x=y;
				qhead++;
				for (i=qhead;i<=tail;i++)
					if (deep[i]>deep[qhead]) qhead=i;
			}
			if (dhead<qhead)
			{
				y=dhead;
				for (i=x+1;i<=y;i++)
					f[i]=tail-i;
				x=y;
				dhead++;
				for (i=dhead;i<=tail;i++)
					if (deep[i]<deep[dhead]) dhead=i;
			}
		}
	}
	if (qhead>dhead)
	{
	for (i=x+1;i<=dhead;i++)
	{
		f[i]=qhead-i+1;
	}
	for (i=dhead+1;i<=n;i++)
		f[i]=n-i+1;
	}
	if (qhead<=dhead)
	{
	for (i=x+1;i<=qhead;i++)
	{
		f[i]=dhead-i+1;
	}
	for (i=qhead+1;i<=n;i++)
		f[i]=n-i+1;
	}
	maxn=0;
	for (i=1;i<=n;i++)
		if (f[i]>maxn) maxn=f[i];
	fout<<maxn;
	fin.close();
	fout.close();
	return 0;
}