80分WA2和10求助!!!

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

2408727188GHR @ 2022-10-25 21:48:09

80分WA2和10求助!!!

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6;

int n, k;
int a[maxn];

void qmax() {
    int *q = new int[maxn], l = 0, r = 0;
    memset(q, 0, sizeof(int) * maxn);
    for (int i = 1; i <= n; i++) {
        while (l < r && q[l] + k <= i)
            l++;
        while (l < r && a[q[r - 1]] < a[i])
            r--;
        q[r++] = i;
        if (i >= k)
            cout << a[q[l]] << " ";
    }
    delete[] q;
}

void qmin() {
    int *q = new int[maxn], l = 0, r = 0;
    memset(q, 0, sizeof(int) * maxn);
    for (int i = 1; i <= n; i++) {
        while (l < r && q[l] + k <= i)
            l++;
        while (l < r && a[q[r - 1]] > a[i])
            r--;
        q[r++] = i;
        if (i >= k)
            cout << a[q[l]] << " ";
    }
    delete[] q;
}

int main() {
    ios::sync_with_stdio(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    qmin();
    cout << endl;
    qmax();
}

by _9192631770_ @ 2022-12-26 14:33:03

第三行maxn再大一些就可以了


|