HDU 5818 – Joint Stacks [左偏树/优先队列]

Link

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

Problem

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.

Mean

有两个栈,支持三种操作,①往其中一个栈push数,②从其中一个栈pop一个数并输出,③将一个栈合并到另外一个栈,按照添加时间顺次合并

Analysis

首先这是一个左偏树(可并堆)的裸题,如果接触过这个数据结构可以直接使用,操作都是log级别的。

另外也可以用三个优先队列模拟一下这个过程,权值是加入时间,对于合并操作,直接放到公共队列,pop不够时从公共里面取即可。

Code1

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;

const int maxn = 152400;

P v[maxn];
int tot, u, a, b,  l[maxn], r[maxn], d[maxn];

int Merge(int x, int y) {
    if(!x) return y;
    if(!y) return x;
    if(v[x] < v[y]) swap(x, y);
    r[x] = Merge(r[x], y);
    if(d[l[x]] < d[r[x]]) swap(l[x], r[x]);
    d[x] = d[r[x]] + 1;
    return x;
}
int init(P x) {
    tot++;
    v[tot] = x;
    l[tot] = r[tot] = d[tot] = 0;
    return tot;
}
int Insert(int x, P y) {
    return Merge(x, init(y));
}
P top(int x) {
    return v[x];
}
int pop(int x) {
    return Merge(l[x], r[x]);
}

char op[30], str[30], str2[30];
int val;

int main() {
    int kase = 0;
    int N;
    while(scanf("%d", &N), N) {
        memset(v, 0, sizeof(v));
        memset(l, 0, sizeof(l));
        memset(r, 0, sizeof(r));
        memset(d, 0, sizeof(d));
        tot = u = a = b = 0;


        printf("Case #%d:\n", ++kase);
        int posA = init(P(-1, -1));
        int posB = init(P(-2, -1));

        for(int i = 1; i <= N; ++i) {
            scanf("%s%s", op, str);
            if(op[1] == 'u') {
                scanf("%d", &val);
                if(str[0] == 'A') {
                    posA = Insert(posA, P(i, val));
                } else {
                    posB = Insert(posB, P(i, val));
                }
            }
            else if(op[1] == 'o') {
                P ans;
                if(str[0] == 'A') {
                    ans = top(posA);
                    posA = pop(posA);
                } else {
                    ans = top(posB);
                    posB = pop(posB);
                }
                printf("%d\n", ans.second);
            }
            else if(op[1] == 'e') {
                scanf("%s", str2);
                if(str[0] == 'A') {
                    posA = Merge(posA, posB);
                    posB = init(P(-i, -1));
                } else {
                    posB = Merge(posA, posB);
                    posA = init(P(-i, -1));
                }
            }
        }
    }
    return 0;
}

Code2

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;

char op[30], str[30], str2[30];

int main() {
    int N, kase = 0;
    while(scanf("%d", &N), N) {
        priority_queue<P> A, B, C;
        printf("Case #%d:\n", ++kase);
        for(int i = 1; i <= N; ++i) {
            scanf("%s%s", op, str);
            if(op[1] == 'u') {
                int val; scanf("%d", &val);
                if(str[0] == 'A') {
                    A.push(P(i, val));
                } else {
                    B.push(P(i, val));
                }
            }
            else if(op[1] == 'o') {
                P ans;
                if(str[0] == 'A') {
                    if(!A.empty()) ans = A.top(), A.pop();
                    else ans = C.top(), C.pop();
                } else {
                    if(!B.empty()) ans = B.top(), B.pop();
                    else ans = C.top(), C.pop();
                }
                printf("%d\n", ans.second);
            }
            else if(op[1] == 'e') {
                scanf("%s", str2);
                while(!A.empty()) {
                    C.push(A.top());
                    A.pop();
                }
                while(!B.empty()) {
                    C.push(B.top());
                    B.pop();
                }
            }
        }
    }
    return 0;
}

欢迎留言