【bzoj2096】Pilots

  • 本文为博主原创，未经许可不得转载\

这题显然使用双指针扫描一遍，然后的问题就是维护区间的最大值和最小值

用线段树可以做到$O(n\log n)$，但是此题的数据范围不支持

考虑用单调队列维护，方法同单调队列经典例题window

感谢cdcq同学帮我查错

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
#define FILE "read"
#define MAXN 3000010
#define cmin(a,b) a=min(a,b)
#define cmax(a,b) a=max(a,b)
int n,k,ans,cur(1),a[MAXN],head[3],tail[3],q[3][MAXN];
inline int read(){
	int x=0,f=1;  char ch=getchar();
	while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
	while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	k=read();  n=read();  head[1]=head[2]=1;
	for(int i=1;i<=n;++i)  a[i]=read();
	for(int i=1;i<=n;++i){
		while(a[i]>a[q[1][tail[1]]]&&head[1]<=tail[1])  tail[1]--;
		while(a[i]<a[q[2][tail[2]]]&&head[2]<=tail[2])  tail[2]--;
		q[1][++tail[1]]=i;
		q[2][++tail[2]]=i;
		while(a[q[1][head[1]]]-a[q[2][head[2]]]>k){
			if(cur==q[1][head[1]]&&head[1]<=tail[1])  ++head[1];
			if(cur==q[2][head[2]]&&head[2]<=tail[2])  ++head[2];
			++cur;
		}
		cmax(ans,i-cur+1);
	}
	printf("%d\n",ans);
	return 0;
}

本文标题:【bzoj2096】Pilots

文章作者:chty

发布时间:2017年03月28日 - 11时25分

最后更新:2018年03月02日 - 17时27分

许可协议:本文为博主原创，未经许可不得转载。

文章目录
,