求大神纠错,为什么wa了一个点?

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

llxyyq @ 2016-11-29 18:29:57

#include<iostream>
#include<cstdio>
using namespace std;
int n,k;
int a[1000006],b[1000006]; 
int head,tail ;
//void pri(){
//    int i;
//    printf("队列"); 
//    for(i=head;i<=tail;i++)
//        printf("%d ",a[b[i]]);
//    printf("\n");
//    printf("坐标");
//    for(i=head;i<=tail;i++)
//        printf("%d ",b[i]);
//    printf("\n");           
//} 
int main(){
    int i;
    scanf("%d %d",&n,&k);
    for(i=0;i<=n-1;i++)
        scanf("%d",&a[i]);
    head=0;
    tail=0;
    b[0]=0;
    i=0;
    while(i<n-1){
        i++;
        while(head<=tail&&a[b[tail]]>a[i]) tail--;
            b[++tail]=i;
        if(tail-head+1>k)
            head++;
        while(head<=tail&&b[head]<=i-k) head++;
        //pri();
        if(i>=k-1)
            printf("%d ",a[b[head]]);        
    }
    printf("\n");
    i=0;
    head=0;
    tail=0;
    b[0]=0;
    while(i<n-1){
        i++;
        while(head<=tail&&a[b[tail]]<a[i]) tail--;
            b[++tail]=i;
        if(head-tail+1>k)
            head++;
        while(head<=tail&&b[head]<=i-k) head++;
        if(i>=k-1)
            printf("%d ",a[b[head]]);
    }
    return 0;  
}

by DeskalLorll @ 2016-11-29 18:59:12

用单调队列吧


|