当前位置 博文首页 > xcc1220的博客:编辑器【简单方法】
????????不瞒你们说,当时我看到这个题的时候,第一反应就是:“这也太简单了吧!”然后的我就一通瞎打,不到20分钟就整了出来。但是,身为一个“带好学生”呢,本着多学一点的精神(其实是为了多在电脑前水一会),京尤上网查找了一下这个题目。不查不知道,一查吓一跳。好家伙,基本上都是用双栈做的,我不禁疑惑,难道我是做了个假题吗?为啥我做的这么简单(可能是我太废了)?所以捏,就像把我的简单方法也分享上来,让大家看看一个弱智天才是怎么做出这道题的(我敢打赌,小白都看得懂我这些代码,嘿嘿嘿(疯狂暗示))。
先看题目!
题目描述
你将要实现一个功能强大的整数序列编辑器。在开始时,序列是空的。编辑器共有五种指令,如下:
1、“I x”,在光标处插入数值x。
2、“D”,将光标前面的第一个元素删除,如果前面没有元素,则忽略此操作。
3、“T”,将光标前的数字减10。
4、“E”,将光标前的三个数字删除。
5、“Q k”,假设此刻光标之前的序列为a1,a2,a3,…ak,输出最大的Si,Si=a1+a2+…+ai(0<i<=x)。
输入描述
第一行包含一个整数n,表示指令的总数。
接下来n行,每行一个指令,具体指令格式如题目描述。
输出描述
每一个“Q k”指令,输出一个整数作为结果,每个结果占一行。
样例
输入
8 I 2 T I -1 I 1 Q 3 D I 5 Q 3输出
-8 -4提示
【数据范围】
0<n<1000000
|x|<1000
0<k<n
?咱先来看看大佬们是咋做的
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define readc(x) scanf("%c",&x) #define read(x) scanf("%d",&x) #define read2(x,y) scanf("%d%d",&x,&y) #define read3(x,y,z) scanf("%d%d%d",&x,&y,&z) #define print(x) printf("%d\n",x) #define mst(a,b) memset(a,b,sizeof(a)) #define pb push_back #define mp make_pair const int inf = 0x3f3f3f3f; const int maxn = 1e6 + 5; int sum[maxn],mx[maxn]; int cnt = 0; stack<int> s,q; int main(){ for(int i = 0 ;i < maxn; i++) mx[i] = -inf; int t; read(t); getchar(); char c; while(t--){ scanf("%c",&c); getchar(); if(c=='I'){ int x; read(x); getchar(); s.push(x); cnt++; sum[cnt] = sum[cnt-1] + x; mx[cnt] = max(mx[cnt-1],sum[cnt]); } if(c=='D'){ if(cnt){ cnt--; s.pop(); } } if(c=='L'){ if(cnt){ cnt--; int top = s.top(); s.pop(); q.push(top); } } if(c=='R'){ if(!q.empty()){ cnt ++; int top = q.top(); q.pop(); s.push(top); sum[cnt] = sum[cnt-1]+top; mx[cnt] = max(mx[cnt-1],sum[cnt]); } } if(c=='Q'){ int x ; read(x); getchar(); print(mx[x]); } } }
看到了吧,大部分人都会这么做。但是,我不一样。ε=(′ο`*)))唉,谁叫我是个
智障天才呢。#include<iostream> #include<cstring> using namespace std; int stack[100011],a[100011]; int top,now,n,op; char x; int fun(){ int max=-1234567890,ans=0; for(int i=0;i<op;i++){ ans+=stack[i]; if(ans>max){ max=ans; } } return max; } int main(){ cin>>n; for(int i=0;i<n;i++){ cin>>x; if(x=='I'){ cin>>stack[top++]; } else if(x=='D'){ top--; } else if(x=='T'){ stack[top-1]-=10; } else if(x=='E'){ top=top-3; } else{ cin>>op; cout<<fun()<<endl; } } }
?懂?我觉得用双栈做是受了题目中“光标”二字的影响,但其实一个栈就可以完成所有的操作了。哎呀呀,不愧是我(得意)。
cs下一篇:没有了