首页 > 代码库 > PAT-l3-002堆栈

PAT-l3-002堆栈

 

L3-002. 堆栈

大家都知道“堆栈”是一种“先进后出”的线性结构,基本操作有“入栈”(将新元素插入栈顶)和“出栈”(将栈顶元素的值返回并从堆栈中将其删除)。现请你实现一种特殊的堆栈,它多了一种操作叫“查中值”,即返回堆栈中所有元素的中值。对于N个元素,若N是偶数,则中值定义为第N/2个最小元;若N是奇数,则中值定义为第(N+1)/2个最小元。

输入格式:

输入第一行给出正整数N(<= 105)。随后N行,每行给出一个操作指令,为下列3种指令之一:

Push key
Pop
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堆栈