单调队列求调

xiaobai0123 @ 2022-11-23 21:37:33

#include <bits/stdc++.h>
using namespace std;
int n,m;
int a[1000];
deque<int>que;
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        while(!que.empty()&&a[que.back()]<a[i])que.pop_back();
        que.push_back(i);
        if(i>=m){
            while(!que.empty()&&que.front()<=i-m)que.pop_front();
            printf("%d ",a[que.front()]);
        }
    }
    puts("");

    return 0;
}

by duchengjun @ 2022-11-23 22:03:03

《 1\le m\le n\le2\times10^6》

by myEnd @ 2022-11-23 22:05:26

@kkk_is_handsome 除了楼上所说，您还要先输出一个“0”。

为什么不先测样例再交呢？

by wukaichen888 @ 2022-11-23 22:06:30

问题好多啊，调吐了（有没有读题啊喂

by XCH_0803 @ 2022-11-23 22:10:00

大家看楼主是不是棕名？

by myEnd @ 2022-11-23 22:12:03

@XCH_0803 我们不应该以名字的颜色来评论别人啊。没准只是被 jc，或者比赛用错帐号了。

by XCH_0803 @ 2022-11-23 22:13:01

@calabash_love_hmz 不是，我只是问一下，怕我眼瞎

by XCH_0803 @ 2022-11-23 22:13:42

@calabash_love_hmz 楼主说他自己还是橙名

by myEnd @ 2022-11-23 22:53:30

@XCH_0803 哦哦哦，好的；刚才说话好像不是很礼貌，真是抱歉（）（