【PAT（甲级）】1057 Stack（关于树状数组的简单解释）

Stack is one of the most fundamental data structures, which is based on the principle of Last In First Out (LIFO). The basic operations include Push (inserting an element onto the top position) and Pop (deleting the top element). Now you are supposed to implement a stack with an extra operation: PeekMedian -- return the median value of all the elements in the stack. With N elements, the median value is defined to be the (N/2)-th smallest element if N is even, or ((N+1)/2)-th if N is odd.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (≤). Then N lines follow, each contains a command in one of the following 3 formats:

 

Push key
Pop
PeekMedian

where key is a positive integer no more than .

Output Specification:

For each Push command, insert key into the stack and output nothing. For each Pop or PeekMedian command, print in a line the corresponding returned value. If the command is invalid, print Invalid instead.

Sample Input:

17
Pop
PeekMedian
Push 3
PeekMedian
Push 2
PeekMedian
Push 1
PeekMedian
Pop
Pop
Push 5
Push 4
PeekMedian
Pop
Pop
Pop
Pop

Sample Output:

Invalid
Invalid
3
2
2
1
2
4
4
5
3
Invalid

解题思路：

1. 对树状数组最好要有个概念，详细的解释我推荐这个博主，他写的真的好https://blog.csdn.net/flushhip/article/details/79165701

2. 这道题目意思就是要求你给栈增加一个功能，能返回栈内第（N/2）或（（N+1）/2）个最小的元素。如果每次都进行排序再输出中间的数字，那么时间上肯定就是超时的。所以，我们把栈内的数字看成是下标，用一个新的数组c[]来存储小于等于这个数字的个数。

新的数组c[ ]是一个树状数组，树状数组的特点就是可以求某一个区间的前缀和，所以每次只要把下标 i 跳到 i 加减 lowbit（i）的位置就可以清楚的知道关于此数字，有多少个小于等于它的数字存在。

因为每次更新树状数组的时候，都是以栈内元素为下标的，所以栈内元素一定是符合第（N/2）或（N+1）/2个中最小的一个值。

代码：

#include
#include
#define max 100001
using namespace std;
int c[max]={0};//用来存储比下标小的数字的个数
stack<int> r;//用来存储给的数字 
 
int lowbit(int a){//树状数组所需要的下标换算 
	return a&(-a);
}
 
void update(int x,int k){
	//x为输入的值也就是c数组下标，增加k就是1，减少k就是-1 
	for(int i = x;i < max;i += lowbit(i)){
		c[i] += k;
	}
}
 
int getSum(int x){//得知比x小的数字的个数 
	int sum = 0;
	for(int i=x;i>0;i-=lowbit(i)){
		sum+=c[i];
	}
	return sum;
} 
 
 
int main(){
	int n;
	scanf("%d",&n);
	for(int i=0;i
		string a;
		a.resize(20);
		int t;
		scanf("%s",&a[0]);
		if(a[1] == 'o'){
			if(r.empty()) printf("Invalid\n");
			else{
				update(r.top(),-1);
				printf("%d\n",r.top());
				r.pop();
			}
		}else if(a[1] == 'u'){
			scanf("%d",&t);
			r.push(t);
			update(t,1);
		}else{
			if(r.empty()) printf("Invalid\n");
			else{
				int left = 1,right = max,mid,k = (r.size()+1)/2;
				while(left
					mid = (right+left)/2;
					if(getSum(mid)>=k){
						//一定是找到等于k的最小的下标 
						right = mid;
					}else{
						left = mid+1;
					}
				}
				printf("%d\n",left);
			}
		}
	}
	return 0;
}