盒子
盒子
文章目录
  1. 题目
  2. 题意
  3. 思路
  4. 代码

POJ 3481 Double Queue(SBT平衡二叉树)

题目

源地址:http://poj.org/problem?id=3481

题意

有一个队伍,一开始为空,有四种操作
0表示结束
1 K P 有一个编号为K的,优先级为P的人加入队伍(队伍中没有相同的K与P)
2 优先级最高的人出队
3 优先级最低的人出队

思路

http://blog.csdn.net/acm_cxlove/article/details/7790305

平衡二叉树,能够得到第K大的数,也能够求出一个数的rank。
这里是找最大值与最小值

代码

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define N 1000005
using namespace std;
struct SBT {
//左子树指针,右子树指针,大小,键值
int left, right, size, key, value;
void Init() {
left = right = key = value = 0;
size = 1;
}
} T[N];
int root, tot; //根的位置以及节点个数
//左旋转处理
void Left_rot(int &x) {
int k = T[x].right;
T[x].right = T[k].left;
T[k].left = x;
T[k].size = T[x].size;
T[x].size = T[T[x].left].size + T[T[x].right].size + 1;
x = k;
}
//右旋转处理
void Right_rot(int &x) {
int k = T[x].left;
T[x].left = T[k].right;
T[k].right = x;
T[k].size = T[x].size;
T[x].size = T[T[x].left].size + T[T[x].right].size + 1;
x = k;
}
//调整处理
void Maintain(int &r, bool flag) {
if(flag) { //更新右子树
if(T[T[T[r].right].right].size > T[T[r].left].size)
Left_rot(r);
else if(T[T[T[r].right].left].size > T[T[r].left].size) {
Right_rot(T[r].right);
Left_rot(r);
} else
return;
} else { //更新在左子树
if(T[T[T[r].left].left].size > T[T[r].right].size)
Right_rot(r);
else if(T[T[T[r].left].right].size > T[T[r].right].size) {
Left_rot(T[r].left);
Right_rot(r);
} else
return;
}
//更新子树,然后再更新根,直到平衡为止
Maintain(T[r].left, false);
Maintain(T[r].right, true);
Maintain(r, false);
Maintain(r, true);
}
//插入新节点
void Insert(int &r, int k, int v) {
if(r == 0) {
r = ++tot;
T[r].Init();
T[r].key = k;
T[r].value = v;
} else {
T[r].size++;
if(k < T[r].key)
Insert(T[r].left, k, v);
else
Insert(T[r].right, k, v);
//插入后要调整,保证平衡
Maintain(r, k >= T[r].key);
}
}
//删除结点,利用的是前驱替换
int Remove(int &r, int k) {
int d_key;
if(!r)
return 0;
T[r].size--;
//前者说明就是要删的节点,后两者说明不存在此节点
if(T[r].key == k || (T[r].left == 0 && k < T[r].key) || (T[r].right == 0 && k > T[r].key)) {
d_key = T[r].key;
if(T[r].left && T[r].right)
T[r].key = Remove(T[r].left, k + 1);
else
r = T[r].left + T[r].right;
} else Remove(k < T[r].key ? T[r].left : T[r].right, k);
}
//取得最大值,即一直遍历到最右的结点
int Get_Max(int r) {
while(T[r].right)
r = T[r].right;
return r;
}
//取得最小值,即一直遍历到最左的结点
int Get_Min(int r) {
while(T[r].left)
r = T[r].left;
return r;
}
//获得前驱
int Get_Pre(int &r, int y, int k) {
if(r == 0) return y;
if(k > T[r].key)
Get_Pre(T[r].right, r, k);
else
Get_Pre(T[r].left, y, k);
}
//获得后继
int Get_Next(int &r, int y, int k) {
if(r == 0) return y;
if(k < T[r].key)
Get_Next(T[r].left, r, k);
else
Get_Next(T[r].right, y, k);
}
//取得第K小的数,注:暂不能解决有重复数的
int Get_Kth(int &r, int k) {
int t = T[T[r].left].size + 1;
if(t == k) return T[r].key;
if(t < k) return Get_Kth(T[r].right, k - r);
else return Get_Kth(T[r].left, k);
}
//获得结点的名次
int Get_Rank(int &r, int k) {
if(k < T[r].key)
return Get_Rank(T[r].left, k);
else if(k > T[r].key)
return Get_Rank(T[r].right, k) + T[T[r].left].size + 1;
else
return T[T[r].left].size + 1;
}
//排序
void Inorder(int &r) {
if(r == 0) return;
Inorder(T[r].left);
printf("%d\n", T[r].key);
Inorder(T[r].right);
}
int main () {
root = tot = 0;
int x, k, p;
while(~scanf("%d", &x)) {
if (!x) break;
if (x == 1) {
scanf("%d%d", &k, &p);
Insert(root, p, k);
}
if (x == 2) {
int tmp = Get_Max(root);
printf("%d\n", T[tmp].value);
if (T[tmp].value) Remove(root, T[tmp].key);
}
if (x == 3) {
int tmp = Get_Min(root);
printf("%d\n", T[tmp].value);
if (T[tmp].value) Remove(root, T[tmp].key);
}
}
return 0;
}