Bzoj2096 [poi2010]pilots

Posted by yjjr's blog on February 6, 2018

标签:单调队列

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)

 

分析:

这题一开始想着用一个队列乱搞,过了半小时搞不出来

看hzwer的博客才发现要维护两个单调队列

和NOIP2016D2T2蚯蚓那题很相像(用三个队列的结论题)

对于此题,考虑每个右端点,它符合题意的左端点序号一定是单调递增的

所以可以用两个单调队列来做,一个保证递增,另一个保证递减

这样我们每次选取两个队列的队头,它们之间的差值一定是最大的,如果不符合题意那么把其中位置靠前的一个队头出队,以此更新答案

Code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#ifdef WIN32
#define LL "%I64d"
#else
#define LL "%lld"
#endif
using namespace std;
inline ll read()
{
	ll f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
const int maxn=3e6+6;
int l1,r1,l2,r2,ans=0,k,n,a[maxn],t,q1[maxn<<1],q2[maxn<<1];
int main()
{
	k=read(),n=read();
	rep(i,1,n)a[i]=read();
    l1=l2=r1=r2=1;
    rep(i,1,n){
    	while(l1<=r1&&a[i]>=a[q1[r1]])r1--;//维护单调下降的队列 
		while(l2<=r2&&a[i]<=a[q2[r2]])r2--;//维护单调上升的队列 
		q1[++r1]=i,q2[++r2]=i;
		while(a[q1[l1]]-a[q2[l2]]>k)
		    if(q1[l1]<q2[l2])t=q1[l1++];
		    else t=q2[l2++];
		ans=max(ans,i-t);
	}
	cout<<ans<<endl;
	return 0;
}



本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr