【BZOJ2096】[Poi2010]Pilots

Description

Tz又耍畸形了！！他要当飞行员，他拿到了一个飞行员测试难度序列，他设定了一个难度差的最大值，在序列中他想找到一个最长的子串，任意两个难度差不会超过他设定的最大值。耍畸形一个人是不行的，于是他找到了你。

Input

输入：第一行两个有空格隔开的整数k（0<=k<=2000,000,000），n(1<=n<=3000,000)，k代表Tz设定的最大值，n代表难度序列的长度。第二行为n个由空格隔开的整数ai（1<=ai<=2000,000,000），表示难度序列。

Output

输出：最大的字串长度。

Sample Input

3 9
5 1 3 5 8 6 6 9 10

Sample Output

4
（有两个子串的长度为4: 5, 8, 6, 6 和8, 6, 6, 9.最长子串的长度就是4）

题解：双指针+单调队列维护最大最小值即可。

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

int n,k,h1,t1,h2,t2,ans;

const int maxn=3000010;

int q1[maxn],q2[maxn],v[maxn];

inline int rd()

{

	int ret=0,f=1;	char gc=getchar();

	while(gc<'0'||gc>'9')	{if(gc=='-')f=-f;	gc=getchar();}

	while(gc>='0'&&gc<='9')	ret=ret*10+gc-'0',gc=getchar();

	return ret*f;

}

int main()

{

	k=rd(),n=rd();

	int i,j;

	for(i=1;i<=n;i++)	v[i]=rd();

	for(h1=h2=i=j=1;i<=n;i++)

	{

		while(h1<=t1&&v[q1[t1]]<=v[i])	t1--;

		q1[++t1]=i;

		while(h2<=t2&&v[q2[t2]]>=v[i])	t2--;

		q2[++t2]=i;

		while(v[q1[h1]]-v[q2[h2]]>k&&j<=i)

		{

			j++;

			while(h1<=t1&&q1[h1]<j)	h1++;

			while(h2<=t2&&q2[h2]<j)	h2++;

		}

		ans=max(ans,i-j+1);

	}

	printf("%d",ans);

	return 0;

}

秒客网

【BZOJ2096】[Poi2010]Pilots 双指针+单调队列