暑期训练之 队列

ACWING.132 小组队列
https://www.acwing.com/problem/content/134/

#include <bits/stdc++.h>
using namespace std;
const int N=1010,M=1000010;
int teamid[M],c=1;
int main(){
    int n;
    while(cin>>n,n){
        cout<<"Scenario #"<<c<<endl;
        c++;
        queue<int> team;
        queue<int> person[N];
        for(int i=0;i<n;i++){
            int cnt;
            cin>>cnt;
            while(cnt--){
                int x;
                cin>>x;
                teamid[x]=i;
            }
        }
        string command;
        while(cin>>command,command!="STOP"){
            if(command=="ENQUEUE"){
                int x;
                cin>>x;
                int tid=teamid[x];
                if(person[tid].empty()) team.push(tid);
                person[tid].push(x);
            }
            else{
                int tid=team.front();
                cout<<person[tid].front()<<endl;
                person[tid].pop();
                if(person[tid].empty()) team.pop();
            }
        }
        cout<<endl;
    }
    return 0;
}

ACWING.135 最大子序和
https://www.acwing.com/problem/content/137/

#include <bits/stdc++.h>
using namespace std;
const int N=300010;
int n,m,sum[N],q[N];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>sum[i];
        sum[i]+=sum[i-1];
    }
    int l=1,r=1,ans=-100000000;
    for(int i=1;i<=n;i++){
        while(l<=r&&q[l]<i-m) l++;
        ans=max(ans,sum[i]-sum[q[l]]);
        while(l<=r&&sum[q[r]]>=sum[i]) r--;
        q[++r]=i;
    }
    cout<<ans<<endl;
    return 0;
}

ACWING.154 滑动窗口
https://www.acwing.com/problem/content/156/

#include <bits/stdc++.h>
using namespace std;
const int N=1000010;
int n,m,a[N],q[N];
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++)cin>>a[i];
    int l=0,r=0;
    for(int i=0;i<n;i++){
        if(l<=r&&q[l]<=i-m) l++;
        while(l<=r&&a[q[r]]>=a[i]) r--;
        q[++r]=i;
        if(i>=m-1) cout<<a[q[l]]<<" ";
    }
    cout<<endl;
    l=0,r=0;
    for(int i=0;i<n;i++){
        if(l<=r&&q[l]<=i-m) l++;
        while(l<=r&&a[q[r]]<=a[i]) r--;
        q[++r]=i;
        if(i>=m-1) cout<<a[q[l]]<<" ";
    }
    cout<<endl;
    return 0;
}