Time Limit Exceeded

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

lizishi @ 2024-07-29 23:10:33

#include <iostream>

#define cap 1000000000000
#define ll long long

using namespace std;

ll max(ll a[], int n, int k, int l) {
    int r = l + k - 1;
    ll max_ = (-1) * cap;
    for (int i = l; i <= r; i++) {
        if (max_ < a[i]) max_ = a[i];
    }
    return max_;
}

ll min(ll a[], int n, int k, int l) {
    int r = l + k - 1;
    ll min_ = cap;
    for (int i = l; i <= r; i++) {
        if (min_ > a[i]) min_ = a[i];
    }
    return min_;
}

int main() {
    int n, k;
    cin >> n >> k;
    ll a[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i <= n - k; i++) {
        cout << min(a, n, k, i) << ' ';
    }
    cout << endl;
    for (int i = 0; i <= n - k; i++) {
        cout << max(a, n, k, i) << ' ';
    }
    return 0;
}
最坏时间复杂度:O(nk - k^2) = O(nk) 输入:1000000$ $500000$ $1<repeat$ $1000000$ $times> 输出:Time$ $Limit$ $Exceeded. 正确输出:1<repeat$ $???$ $times> 时间复杂度要求:O(n) 求助$ $lol$ $QwQ$ $troll:)

by wa_wa_wa_wa @ 2024-07-30 00:25:58

@lizishi 看《模版》后面的四个字,去tj里学吧


by Nemuri @ 2024-08-09 16:47:33

要用单调队列呀


|