Poj 1442堆操作

題意：
給出兩種操作：ADD(x)，將x添加到有序列表中；GET()返回全局迭代器所指的值，其中迭代器在GET操作後會自添加1
題解：
剛開始直接手打鏈表模擬，結果超時。這時應使用另外一種方法：使用大頂堆和小頂堆。
其中，對於序列S[1..n]，及表示迭代器位置的index，大頂堆維護排序後的S[1..index-1]，小頂堆維護
排序後的S[index..n],例如S[1..n] = 1,2,3,4,5,6,7，index = 4，則大頂堆為{1,2,3}，小頂堆為{4,5,6,7}
為什麼要這樣維護呢？因為當小堆最小的元素都大於大堆最大的元素時，那麼序列中排第n個就是小堆最小的數了。
我們假設第k趟GET()後，有以下情景(GET後k自動加1)：
大頂堆：S[1..k]，堆頂元素為S[k]，小頂堆：S[k+1,n]，堆頂元素為S[k+1]，然後每當添加一個元素newE時，先添加到大頂堆中，這時如果出現大頂堆數大於小頂堆的數時，理應交換。
代碼： #include <queue>
#include <stdio.h>
using namespace std;

int m,n;
int sequence[30005];

struct cmp1
{
    bool operator()(const int a,const int b)
    {
        return a>b;
    }
};
struct cmp2
{
    bool operator()(const int a,const int b)
    {
        return a<b;
    }
};

void Test()
{
    priority_queue<int,vector<int>,cmp1>q1;//小堆
    priority_queue<int,vector<int>,cmp2>q2;//大堆

    for (int i = 0; i < m; ++i)
    {
        scanf("%d",&sequence[i]);
    }
    int op;
    int k = 0;
    for (int i = 0; i < n; ++i)
    {
        scanf("%d",&op);
        while(k < op)
        {
            q1.push(sequence[k]);
            if (!q2.empty() && q1.top() < q2.top())
            {
                int t1 = q1.top();
                q1.pop();
                int t2 = q2.top();
                q2.pop();
                q1.push(t2);
                q2.push(t1);
            }
            ++k;
        }
        printf("%d ",q1.top());
        q2.push(q1.top());
        q1.pop();
    }

}

int main()
{
    while(scanf("%d %d",&m,&n) != EOF)
    {
        Test();
    }
    return 0;
}