首页 > 代码库 > 51nod1403 有趣的堆栈
51nod1403 有趣的堆栈
看成括号序列的话第二种方法其实就是左括号和右括号之间有多少对完整的括号。
#include<cstdio>#include<cstring>#include<cctype>#include<algorithm>using namespace std;#define rep(i,s,t) for(int i=s;i<=t;i++)#define dwn(i,s,t) for(int i=s;i>=t;i--)#define clr(x,c) memset(x,c,sizeof(x))int read(){ int x=0;char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) x=x*10+c-‘0‘,c=getchar(); return x;}char s[20];void print(int x){ int cnt=0; while(x) s[++cnt]=x%10,x/=10; dwn(i,cnt,1) putchar(s[i]+48); putchar(32);}const int nmax=1e6+5;int a[nmax],ans[nmax<<1];int main(){ int n=read(),cur=n*2;rep(i,1,n) a[i]=read(); dwn(i,n,1) { while(ans[cur]&&cur) --cur; ans[cur--]=1;ans[cur-a[i]*2]=-1; } int cnt=0; rep(i,1,n*2) { if(ans[i]<0) ++cnt; else{ print(cnt); } } printf("\n"); return 0;}
1403 有趣的堆栈
基准时间限制：1 秒 空间限制：131072 KB 分值: 80 难度：5级算法题
收藏
关注大家都熟悉堆栈操作。一个堆栈一般有两种操作，push和pop。假设所有操作都是合法的并且最终堆栈为空。我们可以有很多方法记录堆栈的操作，
（1） 对每个pop操作，我们记录它之前一共有多少个push操作。
（2） 对每个pop操作，我们记录这个被Pop的元素曾经被压上了几个。
例如：操作push, push, pop, push, push, pop, push, pop, pop, pop
用第一种方法 记录为 2, 4, 5, 5, 5
用第二种方法 记录为 0, 0, 0, 2, 4
这两种记录方法可以互相转化，我们的问题是，给定第二种记录方法的序列，请求出第一种记录方法的序列。
Input
第一行一个整数n，表示序列的长度(0 < n <=1000000)第二行n个整数，表示第二种方法的记录。
Output
一行，空格分隔的n个整数，表示第一种表示方法的序列。
Input示例
50 0 0 2 4
Output示例
2 4 5 5 5
51nod1403 有趣的堆栈
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。