60分求助!!!#2#8#9#10 RE了

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

WA_automat @ 2022-06-24 21:19:42

#include<iostream>
#include<deque>
using namespace std;
int n, k, a[100005];
class MyQueue_big {
public:
    deque<int> que;
    void pop(int value) {
        if (!que.empty() && value == que.front()) {
            que.pop_front();
        }
    }
    void push(int value) {
        while (!que.empty() && value > que.back()) {
            que.pop_back();
        }
        que.push_back(value);
    }
    int front(void) {
        return que.front();
    }
};
class MyQueue_small {
public:
    deque<int> que;
    void pop(int value) {
        if (!que.empty() && value == que.front()) {
            que.pop_front();
        }
    }
    void push(int value) {
        while (!que.empty() && value < que.back()) {
            que.pop_back();
        }
        que.push_back(value);
    }
    int front(void) {
        return que.front();
    }
};
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> k;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    MyQueue_small small;
    MyQueue_big big;
    for (int i = 0; i < k; ++i) {
        small.push(a[i]);
        big.push(a[i]);
    }
    cout << small.front() << ' ';
    for (int i = k; i < n; ++i) {
        small.pop(a[i - k]);
        small.push(a[i]);
        cout << small.front() << ' ';
    }
    cout << endl;
    cout << big.front() << ' ';
    for (int i = k; i < n; ++i) {
        big.pop(a[i - k]);
        big.push(a[i]);
        cout << big.front() << ' ';
    }
    cout << endl;
    return 0;
}

by Fla_Akebono @ 2022-07-14 15:39:40

考虑一下数组a开小了

n<100,000


|