HDU_5249(百度之星D题)

因为之前没写过平衡树的题，所以很自然地只会用set来写。。。然后，很蠢地想直接找set容器中间位置的那个值，结果iterator没有重载+唉。。。翻了一下AC的代码（果然有跟我一样用set来写的），然后发现是两个set容器解决了这个问题。。。其实很容易想到，一个set容器放前一半的数，一个set容器放后一半的数，就行了。。。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <set>
#include <queue>
#define FOR(i,x,y)  for(int i = x;i < y;i ++)
#define IFOR(i,x,y) for(int i = x;i > y;i --)

using namespace std;

int n;

int main()
{
    //freopen("test.in","r",stdin);
    int tCase = 0;
    while(~scanf("%d",&n)){
        printf("Case #%d:
",++tCase);
        int num;
        queue <int> s;
        set <int>   p,q;
        char str[10];
        while(n--){
            getchar();
            scanf("%s",str);
            if(str[0] == 'q'){
                printf("%d
",*(q.begin()));
            }
            else if(str[0] == 'i'){
                scanf("%d",&num);
                s.push(num);
                if(q.empty() || num < *(q.begin())){
                    p.insert(num);
                }
                else
                    q.insert(num);
            }
            else{
                int v = s.front(); s.pop();
                if(p.find(v) != p.end()){
                    p.erase(v);
                }
                else
                    q.erase(v);
            }
            while(p.size() > q.size()){
                set <int> :: iterator it = p.end();
                it--;
                int v = *it;
                p.erase(it);
                q.insert(v);
            }
            while(q.size() > p.size()+1){
                set <int> :: iterator it = q.begin();
                int v = *it;
                p.insert(v);
                q.erase(it);
            }
        }
    }
    return 0;
}