[HNOI 2004] 宠物收养所

题目链接

[BZOJ 1208] [HNOI 2004] 宠物收养所

题解

高档题。题意大概是一个宠物收养所在某一时刻只存在宠物或人,每次来人或宠物时会选取特点值最接近的宠物或人。求特点值之差的总和。
Treap树模板套一套即可。

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

const int MOD = 1000000;
const long long INF = 1ll << 60;
const int MAXN = 80005;

struct Node
{
    int son[2], num, ran;
} treap[MAXN];
int n, ans, q1, q2, root, pd, temploc;

void rotate(int &loc, int drt) {
    int temp = treap[loc].son[drt ^ 1];
    treap[loc].son[drt ^ 1] = treap[temp].son[drt];
    treap[temp].son[drt] = loc;
    loc = temp;
}

void insert(int &loc, int num) {
    if (!loc) {
        loc = ++temploc;
        treap[loc].son[1] = treap[loc].son[0] = 0;
        treap[loc].num = num;
        treap[loc].ran = rand();
        return;
    }
    int temp = num > treap[loc].num;
    insert(treap[loc].son[temp], num);
    if (treap[loc].ran > treap[treap[loc].son[temp]].ran)rotate(loc, temp ^ 1);
}

void remove(int &loc, int num) {
    if (!loc)return;
    if (num == treap[loc].num) {
        if (!treap[loc].son[0] || !treap[loc].son[1]) {
            loc = treap[loc].son[0] + treap[loc].son[1];
            return;
        }
        if (treap[treap[loc].son[0]].ran > treap[treap[loc].son[1]].ran)rotate(loc, 0);
        else rotate(loc, 1);
        remove(loc, num);
    }
    else {
        remove(treap[loc].son[num > treap[loc].num], num);
    }
}

int query(int num) {
    long long pre(-INF), nxt(INF);
    int loc(root);
    while (loc) {
        if (num > treap[loc].num) {
            pre = treap[loc].num;
            loc = treap[loc].son[1];
        }
        else loc = treap[loc].son[0];
    }
    loc = root;
    while (loc) {
        if (num < treap[loc].num) {
            nxt = treap[loc].num;
            loc = treap[loc].son[0];
        }
        else loc = treap[loc].son[1];
    }

    if (nxt - num < num - pre) {
        remove(root, nxt);
        return nxt - num;
    }
    else {
        remove(root, pre);
        return num - pre;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    for (cin >> n; n; n--) {
        cin >> q1 >> q2;
        if (!root || q1 == pd) {
            insert(root, q2);
            pd = q1;
        }
        else {
            ans += query(q2);
            ans %= MOD;
        }
    }
    cout << ans << endl;
}

标签: data structures

添加新评论