其實這個題不該想這么久的。。。
題目的意思是說給一個正數(shù)序列，求其中的最長的
最大值-最小值大于等于
M 并且 小于等于
K 的長度。
咋一看起來很麻煩，想了想也很麻煩。怎么才能保證是最長的并且大于等于M還小于等于K呢？維護一個大于等于M且小于等于K的隊列？當(dāng)加入新的元素之后，若不滿足題目給的條件，應(yīng)該從兩個隊列的隊尾出隊，但是應(yīng)該出哪一個？應(yīng)該出絕對位置靠前面的那個。
上面說了一大堆，忽略了一個問題：當(dāng)兩個隊伍的元素之差小于M的時候，無論怎么出隊，都不可能再大于M了！所以當(dāng)最大值減最小值小于M的時候，就不需要再出隊了。所以程序的自然語言描述就是，維護一個最長的，且<=K的隊列。
上面的思路很麻煩，而且無法證明其正確性。后來發(fā)現(xiàn)這個題就是前幾天比賽A題加了一個條件>=M。好吧，這兩個條件是&&的關(guān)系，直接維護一個小于等于K的隊列即可，不用管那個M了，只要在求結(jié)果的時候判斷下就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;
//保持性質(zhì),更新隊列和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;
}