hack怎么过?

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

ZackofZHOU @ 2024-08-23 10:11:07

代码:

#include<iostream>
#include<deque>
using namespace std;
int n,k,p = 1,a[1000010];
deque <int> d;
int main()
{
    cin >> n >> k;
    for(int i = 1;i <= n;i++)
        cin >> a[i];
    for(int i = 1;i <= n;i++)
    {
        while(!d.empty() && d.back() >= a[i])
            d.pop_back();
        d.push_back(a[i]);
        if(i - p >= k)
        {
            if(a[p] == d.front())
                d.pop_front();
            p++;
        }
        if(i >= k)
            cout << d.front() << ' ';
    }
    cout << '\n';
    p = 1;
    d.clear();
    for(int i = 1;i <= n;i++)
    {
        while(!d.empty() && d.back() <= a[i])
            d.pop_back();
        d.push_back(a[i]);
        if(i - p >= k)
        {
            if(a[p] == d.front())
                d.pop_front();
            p++;
        }
        if(i >= k)
            cout << d.front() << ' ';
    }
    return 0;
}

by Delete_error @ 2024-09-27 13:37:04

当当前值与队列末尾数相等时不弹出


|