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$,对每个元素标记入栈时间。

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

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

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/*************************************************************************
> 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;
}
文章目录
  1. 1. 题目链接:
  2. 2. 题意:
  3. 3. 分析:
  4. 4. 代码: