题目类型 数据结构
题目意思
给出一系列指令 其中
指令 1 插入一个优先级为 B 值为 A 的人
指令2 去掉优先级最高的人并输出这个人的值
指令3 去掉优先级最低的人并输出这个人的值
解题方法
很多方法都可以做 例如 优先队列 线段树 treap 伸展树等
参考代码 - 有疑问的地方在下方留言 看到会尽快回复的
treap
#include <iostream>
#include <cstdio>
#include <ctime>
#include <cstdlib>
using namespace std;
const int maxn = 30000 + 10;
int a[maxn], b[maxn];
struct Node {
Node * ch[2];
int r;
int v;
int msg;
Node(int v, int msg) : v(v), msg(msg) { ch[0] = ch[1] = NULL; r = rand(); }
int cmp(int x) const {
if(x == v) return -1;
return x < v ? 0 : 1;
}
};
struct Treap {
Node * rt;
Treap() { rt = NULL; }
void rotate(Node* & o, int d) {
Node * k = o->ch[d^1]; o->ch[d^1] = k->ch[d]; k->ch[d] = o; o = k;
}
void insert(Node* & o, int x, int msg) {
if(o == NULL) o = new Node(x, msg);
else {
int d = (x > o->v ? 1 : 0); // 相等放左儿子那边
insert(o->ch[d], x, msg);
if(o->ch[d]->r > o->r) rotate(o, d ^ 1);
}
}
void remove(Node* & o, int x) {
int d = o->cmp(x);
if(d == -1) {
Node * u = o;
if(o->ch[0] != NULL && o->ch[1] != NULL) {
int d2 = (o->ch[0] > o->ch[1] ? 1 : 0);
rotate(o, d2); remove(o->ch[d2], x);
}
else {
if(o->ch[0] == NULL) o = o->ch[1]; else o = o->ch[0];
delete u;
}
}
else remove(o->ch[d], x);
}
void removetree(Node* & x) {
if(x == NULL) return ;
if(x->ch[0] != NULL) removetree(x->ch[0]);
if(x->ch[1] != NULL) removetree(x->ch[1]);
delete x;
x = NULL;
}
};
int main() {
freopen("in", "r", stdin);
srand(time(0));
int n;
Treap trp;
while(scanf("%d", &n), n) {
if(n == 1) {
int msg, x;
scanf("%d%d", &msg, &x);
trp.insert(trp.rt, x, msg);
}
else if(n == 2) {
if(trp.rt == NULL) printf("0\n");
else {
Node * t = trp.rt;
while(t->ch[1] != NULL) t = t->ch[1];
printf("%d\n", t->msg);
trp.remove(trp.rt, t->v);
}
}
else {
if(trp.rt == NULL) printf("0\n");
else {
Node * t = trp.rt;
while(t->ch[0] != NULL) t = t->ch[0];
printf("%d\n", t->msg);
trp.remove(trp.rt, t->v);
}
}
}
trp.removetree(trp.rt);
return 0;
}
splay
#include <iostream>
#include <cstdio>
#include <ctime>
#include <cstdlib>
using namespace std;
struct Node {
Node * ch[2];
int v;
int msg;
Node(int v, int msg) : v(v), msg(msg) { ch[0] = ch[1] = NULL; }
int cmp(int x) const {
if(x == v) return -1;
return x < v ? 0 : 1;
}
};
struct Splay {
Node * rt;
Splay() { rt = NULL; }
void rotate(Node* & o, int d) {
Node * k = o->ch[d^1]; o->ch[d^1] = k->ch[d]; k->ch[d] = o; o = k;
}
void splay(Node* & o, int x) {
int d = o->cmp(x);
if(d != -1) {
Node * p = o->ch[d];
int d2 = p->cmp(x);
if(d2 != -1) {
splay(p->ch[d2], x);
if(d == d2) rotate(o, d^1); else rotate(o->ch[d], d);
}
rotate(o, d^1);
}
}
void insert(Node* & o, int x, int msg) {
if(o == NULL) {
o = new Node(x, msg);
splay(rt, x);
}
else {
int d = (x < o->v ? 0 : 1); // avoid repetition
insert(o->ch[d], x, msg);
}
}
int findMax(Node* & o) {
Node * t = o;
while(t->ch[1] != NULL) {
t = t->ch[1];
}
splay(o, t->v);
return o->msg;
}
int findMin(Node* & o) {
Node * t = o;
while(t->ch[0] != NULL) {
t = t->ch[0];
}
splay(o, t->v);
return o->msg;
}
void remove(int x) {
splay(rt, x);
Node * t = rt;
if(rt->ch[0] == NULL) {
rt = rt->ch[1];
delete t;
}
else {
findMax(rt->ch[0]);
rt->ch[0]->ch[1] = rt->ch[1];
rt = rt->ch[0];
delete t;
}
}
};
int main() {
// freopen("in", "r", stdin);
Splay spy;
int n;
while(scanf("%d", &n), n) {
if(n == 1) {
int x, msg;
scanf("%d%d", &msg, &x);
spy.insert(spy.rt, x, msg);
}
else if(n == 2) {
if(spy.rt == NULL) printf("0\n");
else {
printf("%d\n", spy.findMax(spy.rt));
spy.remove(spy.rt->v);
}
}
else {
if(spy.rt == NULL) printf("0\n");
else {
printf("%d\n", spy.findMin(spy.rt));
spy.remove(spy.rt->v);
}
}
}
return 0;
}