HDOJ4006

维持一个整数序列，支持2种操作：

1、增加一个整数到序列中；

2、求序列的第K大的数。

思路：建两个堆，一个小堆来保存前K大的数，一个大堆来保存剩余的数，这样的话，就满足小堆中最小的数也会大于等于大堆中最大的数，在插入的过程中，我们仍需维持这种性质，先将插入的数进入大堆，然后比较2个堆顶的数，若不满足上述性质则交换，直到满足为止。

建大堆：priority_queue<int> qmax;

建小堆：priority_queue<int ,vector<int>,greater<int> >qmin.

#include <stdio.h>
#include <queue>
using namespace std;
int n,k;
int main()
{
    int i,x;
    char c;
    while(~scanf("%d%d",&n,&k))
    {
        priority_queue<int> qmax;
        priority_queue<int,vector<int>,greater<int> >qmin;
        for(i=0;i<n;i++)
        {
            c=0;
            while(c!='I' && c!='Q') scanf("%c",&c);
            if(i<k)
            {
                scanf("%d",&x);
                qmin.push(x);
                continue;
            }
            if(c=='I')
            {
                scanf("%d",&x);
                qmax.push(x);
                while(qmin.top()<qmax.top())
                {
                    int a,b;
                    a=qmin.top(),qmin.pop();
                    b=qmax.top(),qmax.pop();
                    qmin.push(b);
                    qmax.push(a);
                }
            }
            else    printf("%d\n",qmin.top());
        }
    }
    return 0;
}