2016-08-21

HDU 5818 Joint Stacks【优先级队列】

题目链接：

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

题意：

给定栈$A\ B$，有三种操作：$push、pop、merge.$
其中$merge\ A\ B$表示将$B$中元素全部放入$A$中，同时清空$B$，$A$中所有元素按照入栈时间从晚到早排列。
问每次$pop$出的元素。

分析：

引入三个优先级队列$a,b,c$，对每个元素标记入栈时间。

$push$操作正常
对于$merge$操作，将$a,b$清空并将所有元素都放入公共队列$c$中。
由于题目保证不会对空栈进行$pop$操作，假设所操作队列为$a$，若$a$非空，那么$a$中的元素肯定要比$c$中的元素进栈时间晚，直接在$a $中$pop$；否则$a$为空，意味着该元素在公共队列$c$中，直接在$c$中$pop$。

显然每个元素最多进栈$1$次，再加上优先级队列插入的复杂度，总时间复杂度$O(nlogn)$。
优先级队列很容易想到，但是具体细节的巧妙处理还是要多分析一下性质。

代码：

/*************************************************************************
    > File Name: 5818.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com 
    > Created Time: 2016/8/21 12:32:27
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
typedef pair<int,int> p;
priority_queue<p, vector<p>, less<p> >a;
priority_queue<p, vector<p>, less<p> >b;
priority_queue<p, vector<p>, less<p> >c;
char s[10];
char d[10];
int main()
{
    int n;int kas = 1;
    while(~scanf("%d", &n) && n){
        while(!a.empty()) a.pop();
        while(!b.empty()) b.pop();
        while(!c.empty()) c.pop();
        printf("Case #%d:\n", kas++);
		char ch;int x;
        for(int i = 0; i < n; i++){
			scanf("%s", s);
			if(s[1] == 'u'){
				getchar();
				scanf("%c%d", &ch, &x);
				if(ch == 'A') a.push(p(i, x));
				else b.push(p(i, x));
			}else if(s[1] == 'o'){
				getchar();
				scanf("%c", &ch);
				p t;
				if(ch == 'A'){
					if(a.empty()) t = c.top(), c.pop();
					else t = a.top(), a.pop();
				}else{
					if(b.empty()) t = c.top(), c.pop();
					else t = b.top(), b.pop();
				}
				printf("%d\n", t.second);
			}else{
				scanf("%s%s", s, d);
				while(!a.empty()) c.push(a.top()), a.pop();
				while(!b.empty()) c.push(b.top()), b.pop();
			}
		}
    }
    return 0;
}