7-28作业/重写ren_gao_zu

ren_gao_zu · 2025-07-29 11:56:22 · 个人记录

作业

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

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[10000005];
int n,k;
deque<int>dq,pd;
signed main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        while(!pd.empty()&&pd.front()+k<=i){
            pd.pop_front();
        }
        while(!pd.empty()&&a[i]<=a[pd.back()]){
            pd.pop_back();
        }
        pd.push_back(i);
        if(i>=k)cout<<a[pd.front()]<<" ";
    }

    cout<<endl;
    for(int i=1;i<=n;i++){
        while(!dq.empty()&&dq.front()+k<=i){
            dq.pop_front();
        }
        while(!dq.empty()&&a[i]>=a[dq.back()]){
            dq.pop_back();
        }
        dq.push_back(i);
        if(i>=k)cout<<a[dq.front()]<<" ";
    }
    return 0;
}

B3667 求区间所有后缀最大值的位置

#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
int a[10000005];
int n,k;
deque<int>dq;
signed main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        while(!dq.empty()&dq.front()+k<=i){
            dq.pop_front();
        }
        while(!dq.empty()&&a[i]>a[dq.back()]){
            dq.pop_back();
        }
        dq.push_back(i);
        if(i>=k)cout<<dq.size()<<endl;
    }
    return 0;
}

P8661 [蓝桥杯 2018 省 B] 日志统计

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int n,d,k;
//int cnt;
int maxnnn=0;
deque<int>dq;
vector<int>v[100005],hot_id;

void solve(int i){
    //v[i].push_back(100000000);
    while(dq.size())dq.pop_back();
    for(int j=0;j<v[i].size();j++){

        while(dq.size()&&v[i][j]-dq.front()>=d){
            dq.pop_front();
        }
        dq.push_back(v[i][j]);
        if(dq.size()>=k){
            //cnt++;
            hot_id.push_back(i);
            break;
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>d>>k;

    for(int i=1;i<=n;i++){
        int ts,id;
        cin>>ts>>id;
        v[id].push_back(ts);
        maxnnn=max(maxnnn,id);
    }
    for(int i=0;i<=maxnnn;i++){
        sort(v[i].begin(),v[i].end());
        solve(i);
    }//cout<<hot_id.size()<<endl;
    for(auto &x:hot_id ){
        cout<<x<<endl;
    }
    return 0;
}

重写

P2032 扫描

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[10000005];
int n,k;
deque<int>dq;
signed main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        while(!dq.empty()&dq.front()+k<=i){
            dq.pop_front();
        }
        while(!dq.empty()&&a[i]>=a[dq.back()]){
            dq.pop_back();
        }
        dq.push_back(i);
        if(i>=k)cout<<a[dq.front()]<<endl;
    }
    return 0;
}

P1901 发射站（7-27作业重写）

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[10000005],v[1000005],sum[1000005];
stack<int>st;
int maxn=0;
signed main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>v[i];
    }
//  for(int i=0;i<=1e6;i++)
//      b1[i]=-1,b2[i]=-1;
    for(int i=1;i<=n;i++)
    {

        while(st.size()&&a[i]>a[st.top()]){
            sum[i]+=v[st.top()];
            st.pop();
        }
        if(st.size()){
            sum[st.top()]+=v[i];
        }
        st.push(i);
    }
    for(int i=1;i<=n;i++){
        maxn=max(maxn,sum[i]);
    }
    cout<<maxn;
    return 0;
}