整数序列编辑 | Axell's Blog

题目描述

题面

思路

可以建立2个栈,一个存放光标后面的数,一个存放光标前面的数,不断维护答案即可

代码

#include <bits/stdc++.h>
using namespace std;

int f[1000005],ans[1000005],top,tmp,t,cnt,now,step;
char s[10];

stack <int> a;
stack <int> b;

int main(){
    cin>>t;
    for (int i=0;i<=t;++i) ans[i]=-1e9;
    while (t--){
        scanf("%s",s);
        if (s[0]=='I'){
            scanf("%d",&tmp);
            a.push(tmp);
            int top=a.size();
            f[top]=f[top-1]+tmp;
            ans[top]=max(ans[top-1],f[top]);
        }else if(s[0]=='D'){
            a.pop();
        }else if(s[0]=='L'){
            if (!a.empty()){
                int tt=a.top();
                a.pop();
                b.push(tt);
            }
        }else if(s[0]=='R'){
            if (!b.empty()){
                int tt=b.top();
                b.pop();
                a.push(tt);
                int top=a.size();
                f[top]=f[top-1]+tt;
                ans[top]=max(ans[top-1],f[top]);
            }
        }else{
            scanf("%d",&tmp);
            printf("%d\n",ans[tmp]);
        }
    }
    // a.push(1);
    return 0;
}

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License.
Link to this article: https://blog.axell.top/archives/69/