社区讨论

求大佬解释为什么这个手写的单调双端队列维护不对

P1886【模板】单调队列 / 滑动窗口参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@mi6i71qv
此快照首次捕获于
2025/11/20 05:17
4 个月前
此快照最后确认于
2025/11/20 05:17
4 个月前
查看原帖
只有10分QAQ
CPP
#include <cstdio>
#define MAXN 1000010

int head,tail;
int num[MAXN],val[MAXN];
int n,k,a[MAXN];

int main(){
    int t;
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;++i){
        scanf("%d",&a[i]);
    }
    val[0]=a[0];
    ++tail;
    for(int i=1;i<k;++i){
        while(a[i]<num[tail-1]&&head<tail){
            --tail;
        }
        val[tail]=a[i];
        num[tail++]=i;
    }
    printf("%d ",val[head]);
    for(int i=k;i<n;++i){
        while(a[i]<num[tail-1]&&head<tail){
            --tail;
        }
        val[tail]=a[i];
        num[tail++]=i;
        if(i-num[head]==k){
            ++head;
        }
        printf("%d ",val[head]);
    }
//
    printf("\n");
//
    head=0;
    tail=0;
    val[0]=a[0];
    num[0]=0;
    ++tail;
    for(int i=1;i<k;++i){
        while(a[i]>num[tail-1]&&head<tail){
            --tail;
        }
        val[tail]=a[i];
        num[tail++]=i;
    }
    printf("%d ",val[head]);
    for(int i=k;i<n;++i){
        while(a[i]>num[tail-1]&&head<tail){
            --tail;
        }
        val[tail]=a[i];
        num[tail++]=i;
        if(i-num[head]==k){
            ++head;
        }
        printf("%d ",val[head]);
    }
    return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...