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