标题效果：有一个宠物收容所。目前还没有被采纳的宠物或谁想要领养宠物，每个宠物有个性值，大家谁想要领养宠物具有理想人格值。每一刻，宠物收容所只是为了有谁想要领养宠物或宠物的人。
当领走宠物，将有一定程度的不愉快。最低要求是不舒服程度。
思路：就是个模拟+数据结构维护。用set能够水过，时间卡的不是非常紧。练手写了Treap。
注意极大值不能开太大。会re
CODE：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std; struct Complex{
int val,random,cnt,size;
Complex *son[2]; Complex() {
son[0] = son[1] = NULL;
random = rand();
cnt = size = 1;
}
void Maintain() {
size = cnt;
if(son[0] != NULL) size += son[0]->size;
if(son[1] != NULL) size += son[1]->size;
}
int Compare(int x) {
if(x == val) return -1;
return x > val;
}
}*root; int cnt,ans;
int total; int flag; inline void Rotate(Complex *&a,bool dir);
void Insert(Complex *&a,int x);
void Delete(Complex *&a,int x);
int FindSucc(Complex *a,int x);
int FindPred(Complex *a,int x); int main()
{
cin >> cnt;
for(int x,i = 1;i <= cnt; ++i) {
scanf("%d%d",&flag,&x);
if(total > 0) {
if(flag) Insert(root,x),total++;
else {
int pred = FindPred(root,x);
int succ = FindSucc(root,x);
int will_delete = (x - pred <= succ - x) ? pred:succ;
Delete(root,will_delete);
total--;
ans += abs(will_delete - x);
}
}
else if(total < 0) {
if(!flag) Insert(root,x),total--;
else {
int pred = FindPred(root,x);
int succ = FindSucc(root,x);
int will_delete = (x - pred <= succ - x) ? pred:succ;
Delete(root,will_delete);
total++;
ans += abs(will_delete - x);
}
}
else Insert(root,x),total = (flag ? 1:-1);
ans %= 1000000;
}
cout << ans << endl;
return 0;
} inline void Rotate(Complex *&a,bool dir)
{
Complex *k = a->son[!dir];
a->son[!dir] = k->son[dir];
k->son[dir] = a;
a->Maintain(),k->Maintain();
a = k;
} void Insert(Complex *&a,int x)
{
if(a == NULL) {
a = new Complex();
a->val = x;
return ;
}
int dir = a->Compare(x);
if(dir == -1)
a->cnt++;
else {
Insert(a->son[dir],x);
if(a->son[dir]->random > a->random)
Rotate(a,!dir);
}
a->Maintain();
} void Delete(Complex *&a,int x)
{
int dir = a->Compare(x);
if(dir != -1)
Delete(a->son[dir],x);
else {
if(a->cnt > 1)
a->cnt--;
else {
if(a->son[0] == NULL) a = a->son[1];
else if(a->son[1] == NULL) a = a->son[0];
else {
bool _dir = (a->son[0]->random > a->son[1]->random);
Rotate(a,_dir);
Delete(a->son[_dir],x);
}
}
}
if(a != NULL) a->Maintain();
} int FindPred(Complex *a,int x)
{
if(a == NULL) return -INF;
if(a->val > x) return FindPred(a->son[0],x);
return max(a->val,FindPred(a->son[1],x));
} int FindSucc(Complex *a,int x)
{
if(a == NULL) return INF;
if(a->val < x) return FindSucc(a->son[1],x);
return min(a->val,FindSucc(a->son[0],x));
}
版权声明：本文博客原创文章。博客，未经同意，不得转载。