单调队列90pts WA求调 玄关

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

Ascnbeta @ 2024-07-10 14:42:06

rt

#include <bits/stdc++.h>
using namespace std;
int n,k,a[1000007],b[1000007],c[1000007];
int q[1000007],l,r;
int main() {
    scanf("%d%d",&n,&k);
    for (int i = 1; i <= n ; i++) {
        scanf("%d",&a[i]);
    }
    for (int i = 1; i <= n; i++) {
        if (q[l] < i - k + 1) l++;
        while (a[i] <= a[q[r-1]] && l < r) {
            r--;
        }
        q[r++] = i;
        if (i >= k) {
            printf("%d ",a[q[l]]);
        }
    }
    printf("\n");
    l = 0,r = 0;
    memset(q,0,sizeof(q));
    for (int i = 1; i <= n; i++) {
        if (q[l] < i - k + 1) l++;
        while (a[i] >= a[q[r-1]] && l < r) {
            r--;
        }
        q[r++] = i;
        if (i >= k) {
            printf("%d ",a[q[l]]);
        }
    }
    return 0;
} 

手写的队列,没有用STL的双端队列,大佬们帮忙看看哪里有问题


by Ascnbeta @ 2024-07-10 14:55:32

已经自己调好了,此帖结


|