1057 Stack

题目描述
知识点：堆、栈
思路：本题为经典问题，在栈的基础下，需要动态维护一个序列，并且快速z栈找出中位数。
主要思路为加另外大根堆以及小根堆维护中位数。
维护步骤如下：
前提条件：大根堆的元素个数始终比小根堆数目多一或者相等
中位数的查找：就位于大根堆堆顶。
压入一个数：首先判断小根堆是否为空或者插入的数小于小根堆的堆顶元素，则将此元素插入大根堆，反之则插入小根堆。
Pop一个数：先去大根堆里找，如果有则直接删除，没有就说明在小根堆里，删除小根堆的。
adjust调整堆操作：每次压入一个数或者Pop一个数都会导致两个堆元素不满足假设条件。需要执行adjust操作。具体是如果小根堆个数比大根堆个数多，则将小根堆的堆顶元素插到大根堆，直到平衡。如果大根堆个数比小根堆个数大于1，则将大根堆堆顶元素插到小根堆中直到满足条件。

#include
#include
#include
#include
using namespace std;
stack<int> stk;
multiset<int> small,big;
void adjust(){
    while(small.size() > big.size()){
        big.insert(*small.begin());
        small.erase(small.begin());
    }
    while(big.size()-small.size() > 1){
        auto it = --big.end();
        small.insert(*it);
        big.erase(it);
    }
}
int main(){
    int n;
    scanf("%d",&n);
    while(n--){
        char op[20];
        scanf("%s",op);
        if(strcmp(op,"Push")==0){
            int x;
            scanf("%d",&x);
            if(small.empty() || x < *small.begin()) big.insert(x);
            else small.insert(x);
            adjust();
            stk.push(x);
        }else if(strcmp(op,"Pop")==0){
            if(!stk.empty()){
                int x = stk.top();
                stk.pop(); 
                printf("%d\n",x);
                auto it = big.find(x);
                if(it != big.end()) big.erase(it);
                else small.erase(small.find(x));
                adjust();
            }else puts("Invalid");
        }else {
            if(!stk.empty()) printf("%d\n",*(--big.end()));
            else puts("Invalid");
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48