题目链接:128. 编辑器 - AcWing题库
标签:堆顶栈
思路:分别用两个栈,记录光标左边的数和光标右边的数;用s记录前缀和,f记录最大前缀。
对题目所示五个操作有:
1.插入操作:将x插入到L栈中。
2.删除操作:删除L栈的顶部元素。
3.光标左移:将L栈的顶部元素push到R栈
4.光标右移:将R栈的顶部元素push到L栈
5.查询操作:输出f[k]
对于前k个数的最大前缀,可能等于前k-1个数的最大前缀 或者 前k个数的和
即:f[k]=max(f[k-1],s[k])
注意:注意空栈!
代码:
#include<iostream>
#include<stack>
#include<cstring>
using namespace std;const int N = 1000010;int n,x;
char op;
int s[N],f[N];
int l[N],r[N],len1,len2;int main()
{memset(f,-0X3f,sizeof f);cin>>n;for(int i=1;i<=n;i++) {cin>>op;if(op=='I'){cin>>x;l[++len1]=x;s[len1]=s[len1-1]+x;f[len1]=max(f[len1-1],s[len1]);}else if(op=='D'){if(len1>0) len1--;}else if(op=='L'){if(len1>0){x = l[len1];len1--;r[++len2]=x;}}else if(op=='R'){if(len2>0){x = r[len2];len2--;l[++len1]=x;s[len1]=s[len1-1]+x;f[len1]=max(f[len1-1],s[len1]);}}else if(op=='Q'){cin>>x;cout<<f[x]<<endl;}}return 0;
}