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的常用函数(方法)
函数 | 用途 |
---|---|
s.insert() |
插入元素 |
s.count() |
统计元素个数(其实只有1 和0 ) |
s.empty() |
判空 |
s.begin() |
这个set头元素的迭代器 |
s.end() |
这个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;
}