1057. Stack (30)

题目连接：https://www.patest.cn/contests/pat-a-practise/1057

题意：在堆栈中增加一个返回中位数的功能。

一开始我就直接将堆栈中的数移到vector中然后进行排序……

网上看了很多人的答案，根本看不懂，树状数组好难理解啊，等以后再细细理解吧。

参考了http://blog.csdn.net/kakitgogogo/article/details/51926600的解法，高明之处在于省去了将堆栈中元素移动的时间，利用set(默认由小到大排序)，在Push的时候进行判断然后分别压入s1,s2(s2大于mid,s1小于等于mid);

然后Pop和Push操作的时候分被调整s1,s2以及mid的值。保证s1的大小等于s2的大小或者等于s2的大小+1，这样，s1中的最后一个值就是mid;

注意删除的时候要删除的对象是指针，否则将会把所有值相同的元素都删去

 1 #include<stdio.h>
 2 #include<set>
 3 #include<string.h>
 4 #include<stack>
 5 using namespace std;
 6 int mid=100005;
 7 multiset<int>s1,s2;
 8 
 9 void adjust()
10 {
11     multiset<int>::iterator it;
12     if (s1.size()<s2.size())
13     {
14         it=s2.begin();
15         s1.insert(*it);
16         s2.erase(it);
17     }
18     if (s1.size()>s2.size()+1)
19     {
20         it=s1.end();
21         it--;
22         s2.insert(*it);
23         s1.erase(it);
24     }
25     if (!s1.empty())
26     {
27         it=s1.end();
28         it--;
29         mid=*it;
30     }
31 }
32 
33 int main()
34 {
35     int N;
36     scanf("%d",&N);
37     char s[15];
38     stack<int>st;
39     int tmp,v;
40     while (N--)
41     {
42         scanf("%s",s);
43         if (strcmp(s,"Pop")==0)
44         {
45             if (st.size()==0)printf("Invalid
");
46             else{
47                 tmp=st.top();
48             printf("%d
",tmp);
49             st.pop();
50             if (tmp<=mid)s1.erase(s1.find(tmp));
51             else s2.erase(s2.find(tmp));
52             adjust();
53                 }
54         }
55         else if (strcmp(s,"PeekMedian")==0)
56         {
57            if (st.size()==0)printf("Invalid
");
58            else
59            {
60                printf("%d
",mid);
61                //adjust();
62            }
63         }
64         else if (strcmp(s,"Push")==0)
65         {
66             scanf("%d",&v);
67             st.push(v);
68             if (v<=mid)s1.insert(v);
69             else s2.insert(v);
70             adjust();
71         }
72     }
73     return 0;
74 }