POJ3481 Double Queue 题解 （aka 双端优先队列）

题目链接：POJ3481

思路

umm
要维护一个内部有序的 双端队列？

想到平衡树。

但是我几百年前写的 AVL Tree 板子早忘了，因为之前只学过这一个。

C++内部有序的容器——set

set 是内部有序的！（实现是红黑树）

如以下代码：

#include <iostream>
#include <set>
using namespace std;
set<int> homo;
int main()
{
    homo.insert(114);
    homo.insert(1919810);
    homo.insert(114514);
    homo.insert(24);
    homo.insert(514);
    // 注意！这里是“迭代器”——STL中类对象的指针
    for (set<int>::iterator it = homo.begin(); it != homo.end(); it++) {
        cout << *it << endl;
    }
}

输出：

24
114
514
114514
1919810

所以说，set是内部有序的。（据说set是用平衡树实现的）

set的常用函数（方法）

优先双端队列（set实现）（雾

只有大致思路。
插入元素（push）：s.insert(<element>);
弹出最大的元素（pop_max()）：

if (!s.empty()) {
    // 这里的--很重要，因为s.end()返回的是结尾的下一个元素的迭代器
    s.erase(--s.end());
}

弹出最小的元素（pop_min()）：

if (!s.empty()) {
    s.erase(s.begin());
}

读最大的元素（get_max()）：

// 先判空
// rbegin()是指最后一个元素的迭代器
return *(s.rbegin());

读最小的元素（get_min()）：

// 先判空
return *(s.begin());

题解代码

#include <iostream>
#include <set>
using namespace std;
int max_p, min_p;
// 这里是个索引，因为p是唯一的
// 相当于p->k是多对一，k->p是一对多
int p_to_k[10000007];
int opt, p, k, ed;
set<int> waiting_p;

int main()
{
    while (scanf("%d", &opt)) {
        if (opt == 0) {
            // 不要学我
            goto end;
        } else if (opt == 1) {
            scanf("%d%d", &k, &p);
            waiting_p.insert(p);
            p_to_k[p] = k;
        } else if (opt == 2) {
            if (!waiting_p.empty()) {
                ed = *(waiting_p.rbegin());
                waiting_p.erase(--waiting_p.end());
                printf("%d\n", p_to_k[ed]);
                p_to_k[ed] = 0;
            } else {
                printf("0\n");
            }
        } else if (opt == 3) {
            if (!waiting_p.empty()) {
                ed = *(waiting_p.begin());
                waiting_p.erase(waiting_p.begin());
                printf("%d\n", p_to_k[ed]);
                p_to_k[ed] = 0;
            } else {
                printf("0\n");
            }
        }
    }

end:
    return 0;
}