deque 玄学问题求dalao帮忙

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

looloa @ 2023-06-30 23:06:27

贴代码

#include <iostream>
#include <deque>

#define N 1000000

using namespace std;

deque <int> dq;
int n, k, arr[N];

int main(){
    cin >> n >> k;

    for(int i=1; i<=n; i++) cin >> arr[i];

    for(int i=1; i<=n; i++){
        if(dq.front()<i-k+1) dq.pop_front();

        while(!dq.empty()) if(arr[dq.back()]>arr[i]) dq.pop_back();
                           else break;
        dq.push_back(i);
        if(dq.back()>=k) cout << arr[dq.front()] << ' '; 
    }

    dq.clear();
    cout << endl;

    for(int i=1; i<=n; i++){
            if(dq.front()<i-k+1) dq.pop_front();

            while(!dq.empty()) if(arr[dq.back()]<arr[i]) dq.pop_back();
                               else break;
            dq.push_back(i);
            if(dq.back()>=k) cout << arr[dq.front()] << ' '; 
        }
}

奇怪的是, RE on #3, 但下载数据后在本地IDE测试可以正常输出, 在洛谷IDE上则会报错, 这是为什么?是因为IDE对于程序的编译不一样吗?求dalao解惑, 本人感激不尽!


by Killer_joke @ 2023-07-01 07:24:32

@looloa

if(dq.front()<i-k+1) dq.pop_front();

这一句有可能访问空的deque的front 是一个UB

还有

#define N 1000000

当n正好为1000000会越界,建议稍微定义大一点。


by looloa @ 2023-07-01 08:52:48

@Killer_joke

非常感谢dalao的帮助!

此外n等于1000000时还是能过的


|