/*
单调队列
适合解决的问题,多次查询k个连续序列中最大或最小值。可以将复杂度从O(n*n)缩短到O(n)。
实现模式:队列实现,只不过其中元素单调(依次增大或减小),我们假设求最大值。入队时比较队尾元素与插入元素的大小,如果队尾元素小与插入元素,则对尾元素出对,直到大于等于位置。
这样插入k个元素后,队列中队首即为最大值。继续进行第二次查询时,需要比较队首元素在原来元素中的位置,判断是否在这次查询的区间内,如果不在,则出对。使用自定义数组即可实现。
*/
#include <iostream>
using namespace std;
const int nMax = 1000010;
int s[nMax];
int n, k;
struct Queue
{
int pos;
int v;
Queue(){}
Queue(int pos, int v):pos(pos), v(v){}
}MinQueue[nMax], MaxQueue[nMax];//一个最小队列,一个最大队列
int MinLeft, MinRight;
int MaxLeft, MaxRight;
int main()
{
//freopen("e://data.txt", "r", stdin);
while(scanf("%d%d", &n, &k) != EOF)
{
if(!n || !k) continue;
int i;
for(i = 0;i < n; ++ i)
scanf("%d", &s[i]);
MinLeft = MinRight = MaxLeft = MaxRight = 0;
//MinQueue[MinRight ++] = Queue(i, s[i]);
for(i = 0; i < k; ++ i)//队列初始化,其实可以跟下面的合并
{
while(MinRight > 0 && MinQueue[MinRight - 1].v > s[i])
MinRight --;
MinQueue[MinRight ++] = Queue(i, s[i]);
}
printf("%d", MinQueue[MinLeft].v);
for(i;i < n; ++ i)
{
if(MinQueue[MinLeft].pos < i - k + 1)//判断队首元素是否还在查询范围之内
MinLeft ++;
while(MinRight > MinLeft && MinQueue[MinRight - 1].v > s[i])//循环比较队尾元素与插入元素的大小,直到对尾元素大于等于插入元素或者队为空
MinRight --;
MinQueue[MinRight ++] = Queue(i, s[i]);//入队
printf(" %d", MinQueue[MinLeft].v);
}
printf("\n");
for(i = 0; i < k; ++ i)//与上面求最小值相同
{
while(MaxRight > 0 && MaxQueue[MaxRight - 1].v < s[i])
MaxRight --;
MaxQueue[MaxRight ++] = Queue(i, s[i]);
}
printf("%d", MaxQueue[MaxLeft].v);
for(i;i < n; ++ i)
{
if(MaxQueue[MaxLeft].pos < i - k + 1)
MaxLeft ++;
while(MaxRight > MaxLeft && MaxQueue[MaxRight - 1].v < s[i])
MaxRight --;
MaxQueue[MaxRight ++] = Queue(i, s[i]);
printf(" %d", MaxQueue[MaxLeft].v);
}
printf("\n");
}
return 0;
}
分享到:
相关推荐
博客链接 http://blog.csdn.net/CABI_ZGX/article/details/52701138
我的博客链接:http://blog.csdn.net/CABI_ZGX
这是来自poj的一道关于单调队列的题目。分为max_qu和min_qu两部分来做。
poj2823,使用线段树进行查询区域间最大最小值,线段树初步
模拟题 要注意时间的处理 使用优先队列处理请求的事件 进行适当的运算符重载,可以简化代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
poj 2482 Stars in Your Window.md
POJ上的一道题,我感觉挺难的。分享给大家,这是利用拓扑排序实现,也算是拓扑排序的一道例题。有助于大家对拓排的理解
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
相信坦克大战大家都玩过吧,本题就是根据这个游戏设计的。坦克要从起点(Y),到...本题可以使用改进过的广搜或优先队列+bfs 或 记忆化广搜三种方法来解决。第一种方法:改进过的BFS:有些节点需要耗费2个单位时间,要
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告