本文主要是介绍HDU 5818 Joint Stacks （优先队列、链表），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5818
题意：两个栈，可以对其进行push，pop操作，除此之外还有一个操作 merge A, B，是B中的元素合并到A里，然后B清空，注意此时A内元素的顺序还是按照原来初始插入的顺序。让输出每个pop操作的数。
比赛时是用左偏树过的，代码当然是丑陋不堪。后来发现用优先队列进行一个小优化之后也可以过，讨论了一下还有人是用链表做的，很强。
下面是两个优先队列的代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
struct node {int order, key;friend bool operator < (node a, node b) {return a.order < b.order; }
};
int main() {int n;int kase = 1;while(~scanf("%d", &n), n) {priority_queue<node> a, b;getchar();printf("Case #%d:\n", kase++);char ty[10], x[10], y[10];int num;int p = 0;while(n--) {scanf("%s", ty);if(ty[1] == 'u') {scanf("%s %d", x, &num);node tmp;tmp.order = p++;tmp.key = num;if(x[0] == 'A') {a.push(tmp);}else {b.push(tmp);}}else if(ty[1] == 'o') {scanf("%s", x);if(x[0] == 'A') {printf("%d\n", a.top().key);a.pop();}else {printf("%d\n", b.top().key);b.pop();}}else {scanf("%s %s", x, y);if(a.size() < b.size()) { //优化，将较小的队列插入while(!a.empty()) {b.push(a.top());a.pop();}}else {while(!b.empty()) {a.push(b.top());b.pop();}}if(x[0] == 'A') { //若不符合命令，改变两个队列名字的指向即可。if(a.empty()) {swap(a, b);}}else {if(b.empty()) {swap(a, b);}}}}}return 0;
}
这篇关于HDU 5818 Joint Stacks （优先队列、链表）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
