单调队列相关

hjh-已被收容

2025-08-05 09:33:46

发布于：浙江

1阅读

0回复

0点赞

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

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+100;
int Num[N];
int n,k;
deque <int> q;
int main(){
    cin>>n>>k;

    for(int i=1;i<=n;++i){
        cin>>Num[i];
        
        if(!q.empty()&&q.front()<i-k+1){
            q.pop_front();
        }
        while(!q.empty()&&Num[q.back()]>=Num[i]){
            q.pop_back();
        }
        q.push_back(i);
        if(i>=k)cout<<Num[q.front()]<<" ";
    }
    cout<<endl;
    
    q.clear();
    for(int i=1;i<=n;++i){
        if(!q.empty()&&q.front()<i-k+1){
            q.pop_front();
        }
        while(!q.empty()&&Num[q.back()]<=Num[i]){
            q.pop_back();
        }
        q.push_back(i);
        if(i>=k)cout<<Num[q.front()]<<" ";
    }
}

有帮助，赞一个

去预览

0/2000

全部评论 1

hjh-已被收容

A20997.琪露诺

#include<bits/stdc++.h>
using namespace std;
const int N=2*1e5+100;
int Num[N],dp[N];
int n,l,r;
int main(){
    cin>>n>>l>>r;

    for(int i=0;i<=n;++i){
        cin>>Num[i];
    }
    for(int i=1;i<=n;++i){
       dp[i]=INT32_MIN;
    }
    int ans=INT32_MIN;
    deque <int> q;
    for(int i=l;i<=n;i++){
        while(!q.empty()&&dp[i-l]>=dp[q.back()]){
            q.pop_back();
        }
        q.push_back(i-l);
        while(!q.empty()&&q.front()<i-r){
            q.pop_front();
        }
        
        dp[i]=dp[q.front()]+Num[i];
        
        if(i>n-r){
            ans=max(ans,dp[i]);
        }
    }
    cout<<ans;
}

2025-08-05 来自浙江