1057. Stack (30)
分析：
考察树状数组 + 二分， 注意以下几点：
1.题目除了正常的进栈和出栈操作外增加了获取中位数的操作， 获取中位数，我们有以下方法：
(1)：每次全部退栈，进行排序，太浪费时间，不可取。
(2)：题目告诉我们key不会超过10^5，我们可以想到用数组来标记，但不支持快速的统计操作。
(3)：然后将数组转为树状数组，可以快速的统计，再配上二分就OK了。
2.二分中我们需要查找的是一点pos，sum(pos)正好是当前个数的一半，而sum(pos - 1)就不满足。
1 #include <iostream> 2 #include <stdio.h> 3 #include <algorithm> 4 #include <cstring> 5 #include <string> 6 #include <vector> 7 #include <cctype> 8 #include <stack> 9 #include <map> 10 11 using namespace std; 12 13 const int Max_required = 100005; 14 15 int tree_array[Max_required]; 16 17 inline int lowbit(int x) 18 { 19 return x&(-x); 20 } 21 22 void add(int x, int value) 23 { 24 while (x < Max_required) 25 { 26 tree_array[x] += value; 27 x += lowbit(x); 28 } 29 } 30 31 int sum(int x) 32 { 33 int total = 0; 34 while (x > 0) 35 { 36 total += tree_array[x]; 37 x -= lowbit(x); 38 } 39 return total; 40 } 41 42 int binary_find(int x) 43 { 44 int low = 1, high = Max_required, mid; 45 46 while (low <= high) 47 { 48 mid = (low + high) >> 1; 49 int total = sum(mid); 50 51 if (total >= x) 52 high = mid - 1; 53 else if (total < x) 54 low = mid + 1; 55 } 56 return low; 57 } 58 59 int main() 60 { 61 int n; 62 stack<int> st; 63 while (scanf("%d", &n) != EOF) 64 { 65 //st.clear(); 66 memset(tree_array, 0, sizeof(tree_array)); 67 68 char ch[30]; 69 while (n--) 70 { 71 scanf("%s", ch); 72 if (strcmp("Push", ch) == 0) 73 { 74 int pp; 75 scanf("%d", &pp); 76 st.push(pp); 77 add(pp, 1); 78 } 79 else if (strcmp("Pop", ch) == 0) 80 { 81 if (st.empty()) 82 printf("Invalid "); 83 else 84 { 85 printf("%d ", st.top()); 86 add(st.top(), -1); 87 st.pop(); 88 } 89 } 90 else if (strcmp("PeekMedian", ch) == 0) 91 { 92 int len = st.size(); 93 if (len == 0) { 94 printf("Invalid "); 95 continue; 96 } 97 int res = -1; 98 if (len % 2 == 1) 99 res = binary_find((len + 1) / 2); 100 else 101 res = binary_find(len / 2); 102 printf("%d ", res); 103 } 104 } 105 } 106 return 0; 107 }