思路

比较裸的一道平衡树的题。用一个变量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;

}

一言

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

巴特西

[luogu2286][宠物收养所]

思路

代码

一言

最新文章

热门文章