首页 > 代码库 > 1403 有趣的堆栈
1403 有趣的堆栈
1403 有趣的堆栈
基准时间限制：1 秒 空间限制：131072 KB 分值
大家都熟悉堆栈操作。一个堆栈一般有两种操作，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
思路：将序列看成括号匹配；当前最末的肯定是），也就是出栈，那么在这个出栈前有4对括号完整匹配，那么对应这个入栈是在i-2*ans[i]-1,的位置，
那么每次你碰到的未操作的都是），然后每次像上面一样去找入栈点就可以了复杂度O(n）；
1 #include<stdio.h> 2 #include<algorithm> 3 #include<iostream> 4 #include<string.h> 5 #include<stdlib.h> 6 #include<queue> 7 #include<set> 8 #include<vector> 9 #include<map>10 using namespace std;11 typedef long long LL;12 int str[1000005];13 int str1[2*1000005];14 int cnt[1000005];15 inline bool scan_d(int &num) 16 {17 char in;bool IsN=false;18 in=getchar();19 if(in==EOF) return false;20 while(in!=‘-‘&&(in<‘0‘||in>‘9‘)) in=getchar();21 if(in==‘-‘)22 {23 IsN=true;num=0;24 }25 else num=in-‘0‘;26 while(in=getchar(),in>=‘0‘&&in<=‘9‘)27 {28 num*=10,num+=in-‘0‘;29 }30 if(IsN) num=-num;31 return true;32 }33 int main(void)34 {35 int n;36 while(scanf("%d",&n)!=EOF)37 {38 int i,j;39 memset(str1,-1,sizeof(str1));40 for(i = 1; i <= n; i++)41 {42 scanf("%d",&str[i]);43 }44 int u = n;45 for(i = 2*n; i >= 1; i--)46 {47 if(str1[i]==-1)48 {49 str1[i] = 0;50 str1[i-2*str[u]-1] = 1;51 u--;52 }53 }int ac = 0;54 int k = 1;55 for(i = 1;i <= 2*n;i++)56 {57 if(str1[i]==1)58 {59 u++;60 }61 else62 {63 cnt[k++] = u;64 }65 }66 printf("%d",cnt[1]);67 for(i = 2;i <= n;i++)68 {69 printf(" %d",cnt[i]);70 }71 printf("\n");72 }return 0;73 }
1403 有趣的堆栈
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。