首页 > 代码库 > PAT-l3-002堆栈
PAT-l3-002堆栈
L3-002. 堆栈
大家都知道“堆栈”是一种“先进后出”的线性结构,基本操作有“入栈”(将新元素插入栈顶)和“出栈”(将栈顶元素的值返回并从堆栈中将其删除)。现请你实现一种特殊的堆栈,它多了一种操作叫“查中值”,即返回堆栈中所有元素的中值。对于N个元素,若N是偶数,则中值定义为第N/2个最小元;若N是奇数,则中值定义为第(N+1)/2个最小元。
输入格式:
输入第一行给出正整数N(<= 105)。随后N行,每行给出一个操作指令,为下列3种指令之一:
Push keyPop
PeekMedian
其中Push表示入栈,key是不超过105的正整数;Pop表示出栈;PeekMedian表示查中值。
输出格式:
对每个入栈指令,将key入栈,并不输出任何信息。对每个出栈或查中值的指令,在一行中打印相应的返回结果。若指令非法,就打印“Invalid”。
输入样例:17 Pop PeekMedian Push 3 PeekMedian Push 2 PeekMedian Push 1 PeekMedian Pop Pop Push 5 Push 4 PeekMedian Pop Pop Pop Pop输出样例:
Invalid Invalid 3 2 2 1 2 4 4 5 3 Invalid
使用树状数组解决中值问题即可
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<cstdlib> 5 #include<stack> 6 #define maxn 100003 7 using namespace std; 8 int bits[maxn+1]; 9 stack<int>s; 10 void add(int i,int x){//树状数组与二分的结合,pop时不要忘记相减 11 while(i<=maxn){ 12 bits[i]+=x; 13 i+=i&-i; 14 } 15 } 16 int sum(int i){ 17 int s=0; 18 while(i>0){ 19 s+=bits[i]; 20 i-=i&-i; 21 } 22 return s; 23 } 24 int peekmedian(){ 25 int k=int(s.size()+1)>>1,l=1,r=maxn; 26 while(r>l){ 27 int mid=(l+r)>>1; 28 if(sum(mid)>=k){ 29 r=mid; 30 } 31 else{ 32 l=mid+1; 33 } 34 } 35 return r; 36 37 } 38 //树状数组的模板已经构造完成 39 int main(){ 40 int n; 41 scanf("%d",&n); 42 while(n--){ 43 char arr[20]; 44 scanf("%s",arr); 45 if(arr[1]==‘u‘){ 46 int temp; 47 scanf("%d",&temp); 48 s.push(temp); 49 add(temp,1); 50 } 51 else if(arr[1]==‘o‘){ 52 if(!s.empty()){ 53 add(s.top(),-1); 54 printf("%d\n",s.top()); 55 s.pop(); 56 }else{ 57 printf("Invalid\n"); 58 } 59 }else{ 60 if(!s.empty()){ 61 int t=peekmedian(); 62 printf("%d\n",t); 63 } 64 else{ 65 printf("Invalid\n"); 66 } 67 } 68 } 69 }
PAT-l3-002堆栈
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。