单调队列 BZOJ 2096 [Poi2010]Pilots

2096: [Poi2010]Pilots

Time Limit: 30 Sec Memory Limit: 162 MB
Submit: 819 Solved: 418
[Submit][Status][Discuss]

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）

水题一道

从左到右枚举右端点，利用单调队列维护当前区间中的最大值和最小值

如果某一时刻当前区间的最大值和最小值之差超过了k，就向右调整左端点直到差小于等于k为止

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 int n,k,h1,h2,t1,t2,temp=1,ans;
 7 int in[3000010],l1[3000010],l2[3000010];
 8 int main(){
 9     scanf("%d%d",&k,&n);
10     for(int i=1;i<=n;i++) scanf("%d",&in[i]);
11     for(int i=1;i<=n;i++){
12         while(h1<t1&&in[i]<=in[l1[t1-1]]) t1--;
13         while(h2<t2&&in[i]>=in[l2[t2-1]]) t2--;
14         l1[t1]=l2[t2]=i;
15         t1++;t2++; 
16         while(in[l2[h2]]-in[l1[h1]]>k)
17             if(l2[h2]>l1[h1])  temp=l1[h1]+1,h1++;
18             else temp=l2[h2]+1,h2++;
19         ans=max(ans,i-temp+1);
20     }
21     printf("%d",ans);
22     return 0;
23 }