[luogu2286][宠物收养所]

题目链接

思路

比较裸的一道平衡树的题。用一个变量s来表示当前树的情况，当s为负数时树内为宠物，当s为正数时树内为人。然后每次分情况讨论一下。如果树为空或者是与来的东西(人或宠物)与树内存的相同。那么就无法领养，直接将这个东西扔到树里。否则就从树里面找一个与当前值最接近的数字，然后统计进答案。

一开始把inf设的太小了影响了统计答案。

代码

#include<cstdlib>
#include<ctime>
#include<cstdio>
#include<iostream>
#define ls tr[cur].ch[0]
#define rs tr[cur].ch[1]
using namespace std;
typedef long long ll;
const int n = 100000,mod = 1000000;
const ll inf = 1e17 + 10;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
struct node {
    int ch[2],id;
    ll val;
}tr[n];
void rotate(int &cur,int f) {
    int son = tr[cur].ch[f];
    tr[cur].ch[f] = tr[son].ch[f ^ 1];
    tr[son].ch[f ^ 1] = cur;
    cur = son;
}
int tot;
void insert(int &cur,int val) {
    if(!cur) {
        cur = ++tot;
        tr[cur].val = val;
        tr[cur].id = rand();
        return;
    }
    int d = val > tr[cur].val;
    insert(tr[cur].ch[d],val);
    if(tr[tr[cur].ch[d]].id < tr[cur].id) rotate(cur,d);
}
void del(int &cur,int val) {
    if(!cur) return;
    if(val == tr[cur].val) {
        if(!ls || !rs) {cur = ls + rs;return;}
        int d = tr[ls].id > tr[rs].val;
        rotate(cur,d);
        del(cur,val);
    }
    del(tr[cur].ch[val > tr[cur].val],val);
}
ll pred(int cur,int val) {
    if(!cur) return -inf;
    if(val <= tr[cur].val) return pred(ls,val);
    return max(tr[cur].val,pred(rs,val));
}
ll nex(int cur,int val) {
    if(!cur) return inf;
    if(val >= tr[cur].val) return nex(rs,val);
    return min(tr[cur].val,nex(ls,val));
}
int s;
ll ans;
int main() {
    srand(time(0));
    int n = read(),rt = 0;
    while(n--) {
        int bz = read(),x = read();
        if(bz == 0) {
            if(s <= 0) insert(rt,x);
            else {
                int k1 = pred(rt,x),k2 = nex(rt,x);
                int dele = k1;
                if(k2 - x < x - k1) dele = k2;
                ans += abs(dele - x);
                ans %= mod;
                del(rt,dele);
            }
            s--;
        }
        if(bz == 1) {
            if(s >= 0) insert(rt,x);
            else {
                int k1 = pred(rt,x),k2 = nex(rt,x);
                int dele = k1;
                if(k2 - x < x - k1) dele = k2;
                ans += abs(dele - x);
                ans %= mod;
                del(rt,dele);
            }
            s++;
        }
    }
    cout<<ans<<endl;
}

一言

无论做什么，记得为自己而做，那就毫无怨言。 ——流金岁月