首页分享宠物收养所

宠物收养所

来源：萌宠菠菠乐园时间：2024-09-29 22:14

宠物收养所

题目：

http://www.zybbs.org/JudgeOnline/problem.php?id=1208

题目大意：

按时间顺序给出来到动物收养所的动物或收养送物的人，如果来得是动物特征值

是a，那么看否有之前来了收养所的人，如果有，找其中人的特征值与a最接近

的一个人，如果没有着将动物留在收养所，。如果来得是人，着找动物，规则一

样。具体见题目；

思路：

唉，我的思路比较笨，直接搞了两个splayTree，一个是pet，一个是human，

这和我将splayTree封装了应该有很大的关系吧。

我犯的错误：

第一：找最接近k的节点的时候出现了错误，必须将一个节点的左树或者右树（具

体看这个节点和k的大小关系）才能确定最接近k的节点。

第二：删除节点的时候，在删除下面这种情况是出现了错误，rt是要删除的节点

提交情况：wa了若干次， ce了一次

AC code：

#include <cstdio>

#include <cstring>

#include <cstdlib>

#define maxn 1000000

#define mod 1000000

#define INF 2100000000

int min, max;

structsplayTreeNode{

int key, id;

splayTreeNode* son[2],* father;

void init(int k, int chi, splayTreeNode* l, splayTreeNode* r, splayTreeNode* fa){

key = k, id = chi, son[0] = l, son[1] = r, father = fa;

}

};

structsplayTree{

splayTreeNode* nul, *link;

#define root nul->son[0]

int ad, temp;

splayTree(){

link = new splayTreeNode[maxn];

ad = 0;

nul = &(link[ad ++]);

nul->init(0, 0, NULL, NULL, NULL);

}

void rotate(splayTreeNode* &rt, int son1, int son2){

splayTreeNode* temp = rt->son[son1];

rt->son[son1] = temp->son[son2];

if(temp->son[son2] != NULL){

temp->son[son2]->father = rt;

temp->son[son2]->id = son1;

}

temp->son[son2] = rt;

temp->father = rt->father;

temp->id = rt->id;

rt->father = temp;

rt->id = son2;

rt = temp;

}

void splay(splayTreeNode* x, splayTreeNode* rt){

if(x == rt || x->father == rt) return;

splayTreeNode* y = x->father,* z = x->father->father;

if(z == rt){

if(y->son[0] == x) rotate(z->son[y->id], 0, 1);

else rotate(z->son[y->id], 1, 0);

}

else{

if(y->id == x->id){

rotate(z->father->son[z->id], x->id, (x->id)^1);

rotate(y->father->son[y->id], x->id, (x->id)^1);

}

else{

rotate(y->father->son[y->id], x->id, (x->id)^1);

rotate(z->father->son[z->id], y->id, (y->id)^1);

}

splay(x, rt);

}

void insert(int x, int chi, splayTreeNode* &rt, splayTreeNode* rf){

if(rt == NULL){

rt = &link[ad ++];

if(rf == nul) nul->son[0] = root;

rt->init(x, chi, NULL, NULL, rf);

splay(rt, this->nul);

return;

}

if(x < rt->key) insert(x, 0, rt->son[0], rt);

else insert(x, 1, rt->son[1], rt);

}

void remove(splayTreeNode* rt){

if(rt == NULL) return;

if(rt->son[0] == NULL || rt->son[1] == NULL){

if(rt->son[0] == rt->son[1]) rt->father->son[rt->id] = NULL;

else{

temp = (rt->son[0] == NULL) ? 1 : 0;

rt->father->son[rt->id] = rt->son[temp];

rt->son[temp]->father = rt->father;

rt->son[temp]->id = rt->id;

}

splay(rt->father, this->nul);

}

else{

splayTreeNode* tp = rt->son[0];

while(tp->son[1] != NULL) tp = tp->son[1];

if(tp->father == rt){

rt->key = tp->key;

rt->son[0] = tp->son[0];

if(tp->son[0] != NULL) tp->son[0]->father = rt;

}

else{

rt->key = tp->key;

tp->father->son[1] = tp->son[0];

if(tp->son[0] != NULL){

tp->son[0]->father = tp->father;

tp->son[0]->id = 1;

}

splay(rt, this->nul);

}

splayTreeNode* find(int k){

splayTreeNode* rt1 = NULL, * rt2 = NULL;

for(splayTreeNode* tp = this->root; tp != NULL;){

if(k == tp->key){

min = max = k;

return tp;

}

if(tp->key < k){

if(min < tp->key){

min = tp->key;

rt1 = tp;

}

tp = tp->son[1];

}

else{

if(max > tp->key){

max = tp->key;

rt2 = tp;

}

tp = tp->son[0];

}

return (abs(min - k) <= abs(max - k)) ? rt1 : rt2;

}

};

int main(){

int n, a, b;

long long ans;

while(~scanf("%d", &n)){

splayTree pet, human;

ans = 0;

while(n --){

scanf("%d %d", &a, &b);

min = -INF, max = INF;

switch(a){

case 0:

if(human.root != NULL){

splayTreeNode* tp = human.find(b);

ans += abs(b - tp->key);

ans %= mod;

human.remove(tp);

}

else{

pet.insert(b, 0, pet.root, pet.nul);

}

break;

case 1:

if(pet.root != NULL){

splayTreeNode* tp = pet.find(b);

ans += abs(b - tp->key);

ans %= mod;

pet.remove(tp);

}

else{

human.insert(b, 0, human.root, human.nul);

}

break;

}

printf("%lldn", ans);

}

return 0;

}

宠物收养所

推荐分享

缅因猫能长多大一种体型较大的猫

警惕狗贩的骗人损招星期狗的症状特征

宠物收养所

推荐分享

缅因猫能长多大 一种体型较大的猫

警惕狗贩的骗人损招 星期狗的症状特征

缅因猫能长多大一种体型较大的猫

警惕狗贩的骗人损招星期狗的症状特征