其实这个题不该想这么久的。。。
题目的意思是说给一个正数序列，求其中的最长的
最大值-最小值大于等于
M 并且 小于等于
K 的长度。
咋一看起来很麻烦，想了想也很麻烦。怎么才能保证是最长的并且大于等于M还小于等于K呢？维护一个大于等于M且小于等于K的队列？当加入新的元素之后，若不满足题目给的条件，应该从两个队列的队尾出队，但是应该出哪一个？应该出绝对位置靠前面的那个。
上面说了一大堆，忽略了一个问题：当两个队伍的元素之差小于M的时候，无论怎么出队，都不可能再大于M了！所以当最大值减最小值小于M的时候，就不需要再出队了。所以程序的自然语言描述就是，维护一个最长的，且<=K的队列。
上面的思路很麻烦，而且无法证明其正确性。后来发现这个题就是前几天比赛A题加了一个条件>=M。好吧，这两个条件是&&的关系，直接维护一个小于等于K的队列即可，不用管那个M了，只要在求结果的时候判断下就OK。代码如下：
#include <stdio.h>
typedef struct
{
int pos,value;
}node;
node queueMax[1000010],queueMin[1000010];
int mhead,mtail,nhead,ntail;
int data[1000010];
int N,M,K;
int max(int a,int b)
{
if(a > b)
return a;
return b;
}
int main()
{
int res,i;
while(scanf("%d%d%d",&N,&M,&K)!=EOF)
{
for(i=0;i<N;i++)
scanf("%d",&data[i]);
res = 0;
mhead = mtail = nhead = ntail = 0;
node tmp = {0,data[0]};
queueMax[mhead++] = queueMin[nhead++] = tmp;
int start,end; start = 0; end = -1;
while(end < N - 1)
{
//入队列,end++
end++;
while(mtail != mhead && queueMax[mhead - 1].value < data[end])
mhead--;
while(ntail != nhead && queueMin[nhead - 1].value > data[end])
nhead--;
tmp.pos = end;
tmp.value = data[end];
queueMax[mhead++] = queueMin[nhead++] = tmp;
//保持性质,更新队列和start
while(ntail!= nhead && mhead != mtail && (queueMax[mtail].value - queueMin[ntail].value >K))
{
if(queueMax[mtail].pos <= queueMin[ntail].pos)
{
start = queueMax[mtail].pos + 1;
mtail++;
}
else
{
start = queueMin[ntail].pos + 1;
ntail++;
}
}
//找res
if((queueMax[mtail].value - queueMin[ntail].value >= M && queueMax[mtail].value - queueMin[ntail].value<=K) && res < end - start + 1)
res = end - start + 1;
}
printf("%d\n",res);
}
return 0;
}