poj2823(单调队列）

我们知道，上一种算法有一个地方是重复比较了，就是在找当前的f(i)的时候，i的前面k-1个数其它在算f(i-1)的时候我们就比较过了。那么我们能不能保存上一次的结果呢？当然主要是i的前k-1个数中的最大值了。答案是可以，这就要用到单调递减队列。

单调递减队列是这么一个队列，它的头元素一直是队列当中的最大值，而且队列中的值是按照递减的顺序排列的。我们可以从队列的末尾插入一个元素，可以从队列的两端删除元素。

1.首先看插入元素：为了保证队列的递减性，我们在插入元素v的时候，要将队尾的元素和v比较，如果队尾的元素不大于v,则删除队尾的元素，然后继续将新的队尾的元素与v比较，直到队尾的元素大于v,这个时候我们才将v插入到队尾。

2.队尾的删除刚刚已经说了，那么队首的元素什么时候删除呢？由于我们只需要保存i的前k-1个元素中的最大值，所以当队首的元素的索引或下标小于i-k+1的时候，就说明队首的元素对于求f(i)已经没有意义了，因为它已经不在窗里面了。所以当index[队首元素]<i-k+1时，将队首元素删除。（转）

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

struct my{
      int dis;
      int v;
};

const int maxn=1000000+10;

my qmax[maxn],qmin[maxn];
my a[maxn];
int n,k;
int top,last;

bool cmp1(const my &x,const my &y){
     if(x.v==y.v) return x.dis<y.dis;
     return x.v>y.v;
}

bool cmp2(const my &x,const my &y){
    if(x.v==y.v) return x.dis<y.dis;
     return x.v<y.v;
}

void getans1(){
    top=1;
    last=0;
    for (int i=1;i<=n;i++){
         my p=a[i];
         while(p.v>qmax[last].v&&top<=last) --last;
         qmax[++last]=p;
         if(qmax[top].dis<i-k+1) top++;
         if(i>=k)
         printf("%d ",qmax[top].v);
    }
    printf("
");
}

void getans2(){
     top=1;
     last=0;
     for (int i=1;i<=n;i++){
        my p=a[i];
        while(p.v<qmin[last].v&&top<=last) last--;
        qmin[++last]=p;
        if(qmin[top].dis<i-k+1) top++;
        if(i>=k)
        printf("%d ",qmin[top].v);
     }
     printf("
");
}

int main(){
    scanf("%d%d",&n,&k);
    for (int i=1;i<=n;i++){
        scanf("%d",&a[i].v);
        a[i].dis=i;
    }
    getans2();
    getans1();
//
return 0;
}