multiset usage as heap

Middle number

There is a sequence of integers, we have two operations now

1 add a: means add an integer a to the end of the sequence, forms a N+1 long sequence.

2 mid : Output the current sequence's middle numbera sequence's middle number is the middle position of the sequence when it's sorted by in creasing order.(if the sequence's length is even, then the middle position is the litter number's position of the two middle numbers)

example 1, sequence 1 2 13 14 15 16 and it's middle number is 13

example 2, sequence 1 3 5 7 10 11 17 and it's middle number is 7

example 3, 1 1 1 2 3 and it's middle number is 1

Input

The first line of the input gives the number of test cases T, for each test case the first line is the sequence's inital length N, the second line has N number represent the integer sequence. then third line is the operation number M then follows M lines, each line has the format either add a or mid (1<=N<=100000, 0<=M<=10000)

Output

each test case for each mid operation output the middle number

Sample Input

 1
6
1 2 13 14 15 16
5
add 5
add 3
mid
add 20
mid
Sample Output

 5
13
题目分析：数据结构题，使用一个大顶堆与一个小顶堆，时刻维护着大顶堆的元素小于小顶堆元素，并且大顶堆内元素的个与小顶内元素的个数相等或者比后者多一个，故每次查寻的结果都是大顶堆顶元素
n用STL实现堆操作

 

#include<iostream>
#include<set>
using namespace std;

multiset <int> small;
multiset <int, greater<int> > big;


int main()
{
        int cas;
        scanf("%d",&cas);
        while(cas--){
            int n,num;
            scanf("%d",&n);
            small.clear();
            big.clear();
            int nt = n;
            while(nt--){
                scanf("%d",&num);
                small.insert(num);
            }
            for(int i = 0; i < (n+1)/2; i++){
                big.insert(*(small.begin()));
                small.erase(small.begin());
            }
            int m;
            scanf("%d",&m);//getchar();
            char op[100];
            while(m--){
                scanf("%s",&op);
                if(!strcmp(op, "add"))
                {
                    scanf("%d",&num);
                    if(num > *big.begin()){
                        small.insert(num);
                    }
                    else
                    big.insert(num);
                    if(small.size() > big.size()){
                        big.insert(*small.begin());
                        small.erase(small.begin());
                    }
                    else if(big.size() > small.size() + 1){
                        small.insert(*big.begin());
                        big.erase(big.begin());
                    }
                }
                else
                printf("%d\n",*(big.begin()));
            }
        }
        return 0;
}