[PAT解题报告] Stack

难题，不过很经典。题目是维护一个堆栈，除了push, pop外还支持找中位数，中位数就是奇数个数的话，排好顺序中间那个，偶数个数的话第n / 2大的。

分析：

invalid之类的很好判断，堆栈为空再pop或者getMedian就会挂。

维护中位数是难点。经典做法是用两个堆，一个根最大，一个根最小，各存一半元素，保证大根堆存放的是较小的那一半元素，小根堆存放的是较大那一半元素，注意维护两个堆size至多差1。

我采取的是两个multiset，维护的东西差不多。

详细讲讲： s1维护较小的一部分数，s2维护较大的一部分数，时刻保证s1里面最大的不小于s2里面最小的，并且0 <= s1.size() - s2.size() <= 1。这样s1里面最大的就是答案。

如何维护？

(1) 插入x:

(1.1) 若s1和s2的size相同，我们需要把x插入s1，让它大一些，可那样可能会影响顺序。我们把x插入s2,然后把s2里面最小的拿出来放入s1。这样s1比s2多一个元素，并且仍然能维护元素大小关系。

(1.2) 若s1和s2的size不同，我们需要把x插入s2, 但同样可能会影响大小关系。我们把x插入s1，再把s1里面最大的拿出来放入s2，这样s1和s2的size一样大，并且仍然能维护元素大小关系。

(2) 删除x

(2.1) 如果s1和s2的size相同，

(2.1.1) 如果x在s2中，直接删掉它，这样s1比s2多一个元素。

(2.1.2) x在s1中，继续使用之前的方法，从s1中删掉x，并且把s2里面最小的拿出来放到s1, 这里要注意因为之前两个size相同，所以s2肯定不空，拿出最小的不会非法。最后， s1仍然比s2多一个元素。

(2.2) 如果s1和s2的大小不同，则s1比s2多一个元素。

（2.2.1）如果x在s1中，直接删掉它，这样s1和s2的size相同。

(2.2.2) 如果x 在s2中，仍然是先删掉它，再把s1中最大的拿过来放入s2中，这样s1和s2的大小相同。

综上所述，就是集合插入、删除、查找操作。C++ STL很方便。 begin就是最小的，rbegin就是最大的，删除要删除迭代器(iterator),因为直接删掉一个值x的话,multiset会把所有相同的值都删掉，所以如果是反向迭代器rbegin这种删除，就要多一个find再删了。

set的复杂度每次操作是O(logn)的。

代码：

#include <cstdio>
#include <set>
#include <stack>
using namespace std;

multiset<int> s1,s2;
stack<int> st;
char s[100];

int get() {
    return *s1.rbegin();
}

void add(int x) { //add x
    
    if (s1.size() == s2.size()) {
        s2.insert(x);
        s1.insert(*s2.begin());
        s2.erase(s2.begin());
    }
    else {
        s1.insert(x);
        s2.insert(*s1.rbegin());
        s1.erase(s1.find(*s1.rbegin()));
    }
    
}

void remove(int x) {
    multiset<int>::iterator t1 = s1.find(x),t2 = s2.find(x);
    if (s1.size() == s2.size()) {
        if (t2 != s2.end()) {
            s2.erase(t2);
        }
        else {
            s1.erase(t1);
            s1.insert(*s2.begin());
            s2.erase(s2.begin());
        }
    }
    else if (t1 != s1.end()) {
        s1.erase(t1);
    }
    else {
        s2.erase(t2);
        s2.insert(*s1.rbegin());
        s1.erase(s1.find(*s1.rbegin()));
    }
}

int main() {
    int n;
    
    for (scanf("%d",&n);n;--n) {
        scanf("%s",s);
        if (s[1] == 'u') {
            int x;
            scanf("%d",&x);
            st.push(x);
            add(x);
        }
        else if (st.empty()) {
            puts("Invalid");
        }
        else if (s[1] == 'o') {
            printf("%d\n",st.top());
            remove(st.top());
            st.pop();
        }
        else {
            printf("%d\n",get());
        }
        
    }
    return 0;
}

原题链接： http://www.patest.cn/contests/pat-a-practise/1057