一道非常经典的单调队列问题。
使用了递增和递减型两种单调队列。
注意单调队列构造的基本形式
int head=0,tail=1; for(int i=1;i<=m;i++) { while(head<=tail && a[deque[tail]]<=a[i]) tail--; deque[++tail]=i; }
单调队列里一般我们都是存放的数据对应的角标。
本题就是要求对于一个给定的数列,求出他所有的长度为m的子序列的最大值和最小值。
使用单调队列进行维护,输出单调队列队首元素即可。这种代码比较具有对称感。
#include <cstdio> #include <iostream> #define MAXN 1000002 using namespace std; int a[MAXN]; int deque[MAXN]; int n,m; void min_deque() { int head=1; int tail=0; for(int i=1;i<=m;i++) { while(head<=tail && a[deque[tail]]>=a[i]) tail--; deque[++tail]=i; } for(int i=m;i<=n;i++) { while(head<=tail && a[deque[tail]]>=a[i]) tail--; deque[++tail]=i; while(deque[head]<i-m+1) head++; printf("%d",a[deque[head]]); printf( i==n ? "\n" : " "); } } void max_deque() { int head=1; int tail=0; for(int i=1;i<=m;i++) { while(head<=tail && a[deque[tail]]<=a[i]) tail--; deque[++tail]=i; } for(int i=m;i<=n;i++) { while(head<=tail && a[deque[tail]]<=a[i]) tail--; deque[++tail]=i; while(deque[head]<i-m+1) head++; printf("%d",a[deque[head]]); printf( i==n ? "\n" : " "); } } int main() { while(scanf("%d %d",&n,&m)!=EOF) { for(int i=1;i<=n;i++) scanf("%d",&a[i]); min_deque(); max_deque(); } return 0; }
要提交为C++才能过,G++貌似过不了。
相关推荐
博客链接 http://blog.csdn.net/CABI_ZGX/article/details/52701138
我的博客链接:http://blog.csdn.net/CABI_ZGX
poj2823,使用线段树进行查询区域间最大最小值,线段树初步
这是来自poj的一道关于单调队列的题目。分为max_qu和min_qu两部分来做。
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
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题源码
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解题报告
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
北大POJ2002-Squares 解题报告+AC代码
POJ1048,加强版的约瑟夫问题 难度中等
POJ1083的代码,POJ1083的代码,POJ1083的代码