NEUOJ 1117: Ready to declare（单调队列）

题目描述

输入

输出

样例输入

8 3 5 3 2 1 1 10 2 3

样例输出

2 1 1 1 1 2 5 3 2 10 10 10

提示

来源

虽然正解是单调队列，可是我用的是两个栈实现的队列水过的，存下代码

/*************************************************************************     > File Name: Euler.cpp     > Author: acvcla     > QQ:      > Mail: acvcla@gmail.com      > Created Time: 2014年10月30日 星期四 11时19分11秒  ************************************************************************/ #include<iostream> #include<cstring> #include<cstdio> using namespace std; const int maxn=1e5+5; int stack1[maxn],stack2[maxn],max2[maxn],max1,min2[maxn],min1; int top1,top2; void init(){  top1=top2=0;  max1=max2[top2]=0;  min1=min2[top2]=maxn; } int ans1[maxn],ans2[maxn]; void deque(){   if(top2>0){   stack2[--top2];   return ;  }  while(top1>0){   stack2[top2]=stack1[--top1];   max2[top2]=max(top2>0?max2[top2-1]:0,stack2[top2]);   min2[top2]=min(top2>0?min2[top2-1]:maxn,stack2[top2]);   top2++;  }  max1=0;  min1=maxn;  --top2; }  int get_max_min(int x){  if(x)return max(max1,top2>0?max2[top2-1]:0);  return min(min1,top2>0?min2[top2-1]:maxn); } void push(int x){  max1=max(x,max1);  min1=min(x,min1);  stack1[top1++]=x; } int main() {  int n,k,x;  while(~scanf("%d%d",&n,&k)){   init();   int t=0,cnt=0;   for(int i=1;i<=n;i++){    scanf("%d",&x);    push(x);    ++cnt;    if(cnt==k)    {     ans1[t]=get_max_min(0);     //cout<<"sldl"<<endl;     ans2[t++]=get_max_min(1);     deque();     cnt--;    }   }   for(int i=0;i<t;i++)printf("%d%c",ans1[i],i==t-1?'/n':' ');   for(int i=0;i<t;i++)printf("%d%c",ans2[i],i==t-1?'/n':' ');  }  return 0; }