社区讨论

萌新刚学单调队列,咋就tle70分呢

P1440求m区间内的最小值参与者 3已保存回复 5

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
5 条
当前快照
1 份
快照标识符
@mi7xl5dt
此快照首次捕获于
2025/11/21 05:16
4 个月前
此快照最后确认于
2025/11/21 05:16
4 个月前
查看原帖
O(N)O(N)单调队列,就是不能过3个点,跪求大佬,在线等挺急的
CPP
#include<iostream>
#include<deque>
#include<queue>
using namespace std;
long long n,m,mn = 99999999;
struct element{
    long long v,id;
};
deque<element> a;
int main(){
    cin>>n>>m;
    a.push_back({99999999,0});
    cout<<0<<endl;
    for(long long i = 1;i<n;i++){
        long long x;
        cin>>x;
        if(x<a.back().v){
            while(!a.empty()&&x<a.back().v){
                a.pop_back();
            }
        }
        a.push_back({x,i});
        cout<<a.front().v<<endl;
        if(a.front().id==i-m+1)a.pop_front();
    }
    return 0;
}

回复

5 条回复,欢迎继续交流。

正在加载回复...