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