「HNOI2004」宠物收养所 - set

有 N（<= 80000）个宠物或领养者，每个宠物或者领养者有一个特点值 a，每次当宠物或领养者到来时，从已有的当中匹配一个与其特点值相差最小（且特点值较小）的并删除，计算所有的领养特点值差的总和。

链接

题解

匹配相差最小的元素，很容易联想到复杂度为的二分查找，但是题目要求动态插入删除，考虑使用 STL 中的 set。

为宠物和领养者各维护一个 set，每当有新的到来时，从另一个 set 中 lower_bound 找出第一个大于等于该特点值的元素，该元素的上一个即为第一个小于该特点值的元素，取二者与新加入的特点值相差较小的即可。

代码

#include <cstdio>
#include <set>
#include <algorithm>

inline bool isempty(char ch) {
    return ch != '-' && (ch < '0' || ch > '9');
}

template <typename T>
inline void read(T &x) {
    x = 0;
    register char ch;
    while (isempty(ch = getchar()));

    register bool flag = false;
    if (ch == '-') {
        flag = true;
        ch = getchar();
    }

    do {
        x = x * 10 + (ch - '0');
    } while (!isempty(ch = getchar()));

    if (flag) {
        x = -x;
    }
}

const unsigned int MAXN = 80000;
const unsigned int p = 1000000;

std::set<unsigned int> pets, owners;
unsigned int n, ans;

inline unsigned int diff(unsigned int x, unsigned int y) {
    return std::max(x, y) - std::min(x, y);
}

inline void add(unsigned int x, unsigned int y) {
    ans = (ans + (diff(x, y) % p)) % p;
}

inline void solve(std::set<unsigned int> &set, unsigned int x) {
    if (set.size() == 1) {
        add(x, *set.begin());
        set.clear();
    } else {
        std::set<unsigned int>::const_iterator r = set.lower_bound(x);

        if (r == set.begin()) {
            add(x, *r);
            set.erase(r);
        } else {
            std::set<unsigned int>::const_iterator l = --set.lower_bound(x);

            if (r == set.end() || diff(x, *l) <= diff(x, *r)) {
                add(x, *l);
                set.erase(l);
            } else {
                add(x, *r);
                set.erase(r);
            }
        }
    }
}

int main() {
    read(n);

    for (unsigned int i = 0; i < n; i++) {
        register unsigned int type, x;
        read(type), read(x);

        if (type == 0) { // pet
            if (owners.empty()) {
                pets.insert(x);
            } else {
                solve(owners, x);
            }
        } else { // owner
            if (pets.empty()) {
                owners.insert(x);
            } else {
                solve(pets, x);
            }
        }
    }

    printf("%u\n", ans);

    return 0;
}