HDU 5818 Joint Stacks （优先队列）

Joint Stacks

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=5818

Description

A stack is a data structure in which all insertions and deletions of entries are made at one end, called the "top" of the stack. The last entry which is inserted is the first one that will be removed. In another word, the operations perform in a Last-In-First-Out (LIFO) manner. A mergeable stack is a stack with "merge" operation. There are three kinds of operation as follows: ``` - push A x: insert x into stack A - pop A: remove the top element of stack A - merge A B: merge stack A and B ``` After an operation "merge A B", stack A will obtain all elements that A and B contained before, and B will become empty. The elements in the new stack are rearranged according to the time when they were pushed, just like repeating their "push" operations in one stack. See the sample input/output for further explanation. Given two mergeable stacks A and B, implement operations mentioned above.

Input

There are multiple test cases. For each case, the first line contains an integer N(0 < N ≤ 105), indicating the number of operations. The next N lines, each contain an instruction "push", "pop" or "merge". The elements of stacks are 32-bit integers. Both A and B are empty initially, and it is guaranteed that "pop" operation would not be performed to an empty stack. N = 0 indicates the end of input.

Output

For each case, print a line "Case #t:", where t is the case number (starting from 1). For each "pop" operation, output the element that is popped, in a single line.

Sample Input

4 push A 1 push A 2 pop A pop A 9 push A 0 push A 1 push B 3 pop A push A 2 merge A B pop A pop A pop A 9 push A 0 push A 1 push B 3 pop A push A 2 merge B A pop B pop B pop B 0

Sample Output

Case #1: 2 1 Case #2: 1 2 3 0 Case #3: 1 2 3 0

Source

2016 Multi-University Training Contest 7
##题意：给出两个栈A B(初始时为空)，有三种操作： push、pop、merge. 其中merge是按照A B中元素进栈的相对顺序来重排的.
##题解：给每次push的数加上一个时间戳. 维护三个优先队列，按照节点的进栈时间从后往前排序(时间戳从大往小). 这样就保证了列首元素一定是最晚进栈的. 三个优先队列：A和B为题中的栈，COM为公共栈. (即存放合并后的结果，并标记COM当前是A还是B) ①对于push操作，按照正常逻辑入栈(入队). ②对于pop操作，先从A/B中去找，如果A/B为空，则说明存放在COM公共栈中了. (题目保证了不会对空栈pop，这样一来都不需要再额外标记公共栈COM当前是A还是B了). ③对于merge操作，把当前A和B全部清空并放到公共栈COM中即可. 可以证明，每个元素被移动到COM中的次数不超过1. 所以总体时间复杂度还是O(n).
官方题解说的是直接用三个栈来模拟，那么对于merge操作时，要用双指针比较来决定入栈顺序. 题解还说可以用链表模拟，遗憾的是一开始就用std::list来做，然后莫名RE.... (想太复杂了，瞎搞了两个小时).
##代码： ``` cpp #include #include #include #include #include #include #include #include #include #include #define LL long long #define eps 1e-8 #define maxn 1010 #define mod 100000007 #define inf 0x3f3f3f3f #define mid(a,b) ((a+b)>>1) #define IN freopen("in.txt","r",stdin); using namespace std;

typedef pair<int,int> pii;
priority_queue com;
priority_queue a;
priority_queue b;

int main(int argc, char const *argv[])
{
//IN;

int n; int ca = 1;
while(scanf("%d", &n) != EOF && n)
{
    printf("Case #%d:
", ca++);
    while(!a.empty()) a.pop();
    while(!b.empty()) b.pop();
    while(!com.empty()) com.pop();

    int time_cnt = 0;

    while(n--) {
        char op[10]; char aim;
        scanf("%s %c", op,&aim);
        if(op[1] == 'u') {
            int x; scanf("%d", &x);
            if(aim == 'A') {
                a.push(make_pair(time_cnt++, x));
            } else {
                b.push(make_pair(time_cnt++, x));
            }
        }
        else if(op[1] == 'o') {
            if(aim == 'A') {
                if(!a.empty()) {
                    pii x = a.top(); a.pop();
                    printf("%d
", x.second);
                } else {
                    pii x = com.top(); com.pop();
                    printf("%d
", x.second);
                }
            } else {
                if(!b.empty()) {
                    pii x = b.top(); b.pop();
                    printf("%d
", x.second);
                } else {
                    pii x = com.top(); com.pop();
                    printf("%d
", x.second);
                }
            }
        }
        else {
            char tmp[10]; gets(tmp);
            while(!a.empty()) {
                pii x = a.top();
                a.pop();
                com.push(x);
            }
            while(!b.empty()) {
                pii x = b.top();
                b.pop();
                com.push(x);
            }
        }
    }
}

return 0;

}