比赛 20120419s 评测结果 AAAAAAAAAA
题目名称 河床 最终得分 100
用户昵称 QhelDIV 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2012-04-19 10:13:29
显示代码纯文本
/*
method:优先队列
prob:riverbed
*/
#include <fstream>
using namespace std;
ifstream fin("riverbed.in");
ofstream fout("riverbed.out");
int n,k,A[50000],Tk=1;
class pq
{
public:
	int Data[50000],Ti[50000],head,tail;
	pq()
	{
		head=1;tail=0;
	}
	void up()
	{
		while(Ti[head]<Tk && head<tail)
			head++;
	}
	void pushback(int Tar,int Pos,int type)
	{
		while(Ti[head]<Tk && head<tail)
			head++;
		if(type==1)
			while(Tar>Data[tail] && head<=tail)
				tail--;
		if(type==2)
			while(Tar<Data[tail] && head<=tail)
				tail--;
		tail++;
		Ti[tail]=Pos;
		Data[tail]=Tar;
	}
}Max,Min;
void Initialize()
{
int i;
	fin>>n>>k;
	for(i=1;i<=n;i++)
		fin>>A[i];
}

void pq()
{
int i=1,Mx=-2000000;
	for(;i<=n;)
	{
		Max.pushback(A[i],i,1);
		Min.pushback(A[i],i,2);
		while(Max.Data[Max.head]-Min.Data[Min.head] >k)
			{Tk++;Max.up();Min.up();}
		if(i-Tk+1>Mx)
			Mx=i-Tk+1;
		i++;
	}
	fout<<Mx<<endl;
}

int main()
{
	Initialize();
	
	pq();
	
	fin.close();
	fout.close();
	return 0;
}