首页 > 代码库 > 单调队列 poj2823,fzu1894
单调队列 poj2823,fzu1894
题目链接：http://poj.org/problem?id=2823
用RMQ超时了，我想应该是不会的，看discuss说，之前RMQ过了。
维护两个单调队列。
单调递减的队列，每插入一个时：
超过单调队列长度，左移头指针。
第一个或者符合条件，直接加到后面。
否则，一直退；
1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> 4 #include <cstring> 5 6 using namespace std; 7 8 const int N = 1000000 + 5; 9 10 int n,m;11 int a[N],q[N];12 13 void MinQ()14 {15 int h=1,t=0;16 q[1] = 1;17 for(int i=1;i<=n;i++) {18 if(i-q[h]==m) h++;19 20 if(t==h-1||a[i]>a[q[t]]) {21 t++;22 q[t] = i;23 }24 else {25 while(t>=h&&a[i]<=a[q[t]])26 {27 q[t] = i;28 t--;29 }30 t++;31 }32 if(i>=m) printf("%d ",a[q[h]]);33 34 }35 puts("");36 }37 38 void MaxQ()39 {40 int h=1,t=0;41 q[1] = 1;42 for(int i=1;i<=n;i++) {43 44 if(i-q[h]==m) h++;45 46 if(t==h-1||a[i]<a[q[t]]) {47 t++;48 q[t] = i;49 }50 else {51 while(t>=h&&a[i]>=a[q[t]])52 {53 q[t] = i;54 t--;55 }56 t++;57 58 }59 if(i>=m) printf("%d ",a[q[h]]);60 61 }62 }63 64 int main()65 {66 cin>>n>>m;67 for(int i=1;i<=n;i++) {68 scanf("%d",&a[i]);69 }70 71 MinQ();72 MaxQ();73 74 return 0;75 }
题目链接：http://acm.fzu.edu.cn/problem.php?pid=1894
和单调递增队列一样。
1 /* 2 RunID: 727738 3 UserID: TreeDream 4 Submit time: 2017-02-16 00:04:08 5 Language: C++ 6 Length: 1167 Bytes. 7 Result: Accepted 8 */ 9 10 //#include <bits/stdc++.h>11 #include <iostream>12 #include <cstdio>13 #include <algorithm>14 #include <cstring>15 16 17 using namespace std;18 19 const int maxn = 1000000 + 5;20 int a[maxn];21 int q[maxn];22 23 int main()24 {25 //freopen("in.txt","r",stdin);26 int t;27 scanf("%d",&t);28 29 while(t--)30 {31 char op[10];32 scanf("%s",op);33 34 int head = 1,tail = 0;35 36 q[0] = -1;37 38 int i=0,j=1;39 char cmd[10],name[10];40 int len = 0;41 42 while(scanf("%s",cmd))43 {44 if(strcmp(cmd,"END")==0) break;45 46 if(cmd[0]==‘C‘) //插入是有条件的47 {48 scanf("%s",name);49 len ++;50 scanf("%d",&a[len]);51 while(head<=tail&&a[q[tail]]<=a[len])52 tail--;53 q[++tail] = len;54 }55 56 else if(cmd[0]==‘G‘)57 {58 while(head<=tail&&q[head]<=j)59 head++;60 j++;61 }62 else printf("%d\n",head>tail?-1:a[q[head]]);63 }64 }65 66 return 0;67 }
参考：http://blog.csdn.net/acdreamers/article/details/20911981
单调队列 poj2823,fzu1894
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。