POJ 2823 单调队列

题意：

有N个数，每次从左至右选M个数，即[1..M]，[2..M+1]，…，[M-N+1..N]，选取每个区间的最大值和最小值。

解题分析：

明显的单调队列解决，复杂度O(N)

但是却跑了6000+MS。不知道那些500MS的怎么跑出来的。

code：

#include #define N 1000001
using namespace std;

int n,m,a[N],qf[N],qn[N];

void init(){
     scanf("%d%d",&n,&m);
     for (int i=1;i<=n;i++)
       scanf("%d",&a[i]);
}

void work1(){
     int head=1,tail=0;
     for (int i=1;i         while (head<=tail && qf[tail]>=a[i]) tail--;
         tail++;
         qf[tail]=a[i];
         qn[tail]=i;
     }
     for (int i=m;i<=n;i++){
         while (head<=tail && qf[tail]>=a[i]) tail--;
         tail++;
         qf[tail]=a[i];
         qn[tail]=i;
         while (qn[head]         printf("%d",qf[head]);
         if (i!=n) cout << " ";
     }
     cout << endl;
}

void work2(){
     int head=1,tail=0;
     for (int i=1;i         while (head<=tail && qf[tail]<=a[i]) tail--;
         tail++;
         qf[tail]=a[i];
         qn[tail]=i;
     }
     for (int i=m;i<=n;i++){
         while (head<=tail && qf[tail]<=a[i]) tail--;
         tail++;
         qf[tail]=a[i];
         qn[tail]=i;
         while (qn[head]         printf("%d",qf[head]);
         if (i!=n) cout << " ";
     }
     cout << endl;

}

int main(){
    init();
    work1();
    work2();
    return 0;
}