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
5 1 3 5 8 6 6 9 10
Sample Output
4
(有两个子串的长度为4: 5, 8, 6, 6 和8, 6, 6, 9.最长子串的长度就是4)
(有两个子串的长度为4: 5, 8, 6, 6 和8, 6, 6, 9.最长子串的长度就是4)
HINT
Source
题解:
http://hzwer.com/5235.html
code:
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
char ch;
bool ok;
void read(int &x){
for (ok=,ch=getchar();!isdigit(ch);ch=getchar()) if (ch=='-') ok=;
for (x=;isdigit(ch);x=x*+ch-'',ch=getchar());
if (ok) x=-x;
}
const int maxn=;
int k,n,v,hmin,tmin,hmax,tmax,ans,last;
struct Data{
int val,id;
}qmin[maxn],qmax[maxn];
int main(){
read(k),read(n);
hmin=hmax=,tmin=tmax=,last=;
for (int i=;i<=n;i++){
read(v);
while (hmin<=tmin&&qmin[tmin].val>v) tmin--;
qmin[++tmin]=(Data){v,i};
while (hmax<=tmax&&qmax[tmax].val<v) tmax--;
qmax[++tmax]=(Data){v,i};
while (hmin<=tmin&&hmax<=tmax&&qmax[hmax].val-qmin[hmin].val>k)
if (qmax[hmax].id<qmin[hmin].id) last=qmax[hmax++].id+;
else last=qmin[hmin++].id+;
ans=max(ans,i-last+);
}
printf("%d\n",ans);
return ;
}