求大神纠错

P1886 滑动窗口 /【模板】单调队列

WLQ567 @ 2016-11-14 19:55:07

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>        
using namespace std;
const int maxn=1000000+100;
int n,k;
int a[maxn];
int read(){
    int n=0,sign=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')sign=-1;c=getchar();}
    while(c>='0'&&c<='9')n=n*10+c-'0',c=getchar();
    return n*sign;
}
int mx[maxn][25],mi[maxn][25];
void init(){
    for(int i=1;i<=n;i++)mx[i][0]=mi[i][0]=a[i];
    int m=(int)(log(n*1.0)/log(2.0));
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            if(j+(1<<(i-1))<=n){
                mx[j][i]=max(mx[j][i-1],mx[j+(1<<(i-1))][i-1]);
                mi[j][i]=min(mi[j][i-1],mi[j+(1<<(i-1))][i-1]);
            }
    return ;
}
int rmqmax(int l,int r){
    int m=(int)(log((r-l+1)*1.0)/log(2.0));
    return max(mx[l][m],mx[r-(1<<m)+1][m]);
}
int rmqmin(int l,int r){
    int m=(int)log(((r-l+1)*1.0)/log(2.0));
    return min(mi[l][m],mi[r-(1<<m)+1][m]);
}
int main(){
    n=read(),k=read();
    for(int i=1;i<=n;i++)a[i]=read();
    init();
    for(int i=1;i<=n-k+1;i++)printf("%d ",rmqmin(i,i+k-1));
    printf("\n");
    for(int i=1;i<=n-k+1;i++)printf("%d ",rmqmax(i,i+k-1));
    return 0;
}

by winmt @ 2016-11-14 20:43:54

写那么麻烦干什么,还用rmq?!

直接C++-STL-priority_queue建个大根堆和小根堆就过了~不会TLE的。


|