本蒟蒻想要求助，大佬能不能帮忙看一看

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

cyt123bc @ 2024-04-13 16:20:54

[p1886]提交记录本蒟蒻用的是单调队列，目前只得90分。

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6+50;
int a[N], q[N];
int n, k;

int main () {
    cin >> n >> k;
    int h = 0, t = -1;

    for (int i = 1; i <= n; i++) {
        scanf("%d",&a[i]);
        while (h <= t && i - k >= q[h]) {
            h++;
        }
        while (h <= t && a[q[t]] >= a[i]) {
            t--;
        }
        q[++t] = i;
        if (i >= k) {
            printf("%d ",a[q[h]]);
        }
    }
    cout << "\n";

    for (int i = 1; i <= n; i++) {
        while (h <= t && i - k >= q[h]) {
            h++;
        }
        while (h <= t && a[q[t]] <= a[i]) {
            t--;
        }
        q[++t] = i;
        if (i >= k) {
            printf("%d ",a[q[h]]);
        }
    }

    return 0;
}

by Li_Feiy @ 2024-04-13 16:28:12

@cyt123bc 你求了最小值之后没有清空

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6+50;
int a[N], q[N];
int n, k;

int main () {
    cin >> n >> k;
    int h = 0, t = -1;

    for (int i = 1; i <= n; i++) {
        scanf("%d",&a[i]);
        while (h <= t && i - k >= q[h]) {
            h++;
        }
        while (h <= t && a[q[t]] >= a[i]) {
            t--;
        }
        q[++t] = i;
        if (i >= k) {
            printf("%d ",a[q[h]]);
        }
    }
    cout << "\n";
    h=0,t=0;
    for (int i = 1; i <= n; i++) {
        while (h <= t && i - k >= q[h]) {
            h++;
        }
        while (h <= t && a[q[t]] <= a[i]) {
            t--;
        }
        q[++t] = i;
        if (i >= k) {
            printf("%d ",a[q[h]]);
        }
    }

    return 0;
}

by cyt123bc @ 2024-04-14 15:12:26

@Li_Feiy 谢谢，A了