思路与算法

等待集合为空时记录当前类型；同类型到达就插入有序set。相反类型到达时，用lower_bound找到第一个不小于目标的特点值，并与其前驱比较距离。距离相同选较小特点值，累加差值后删除被配对项。

正确性说明

由于每次相反类型立即配对，等待集合始终只有一种类型。有序集合中目标左侧最优者必为最大前驱，右侧最优者必为最小后继，其他元素不会更近；比较这两个候选就能按题目规则唯一选择。删除匹配项、保留未匹配项使下一次集合与实际收养所状态一致，归纳可得所有不满意度准确。

复杂度

n≤8万，等待量≤1万，每次插入/查找/删除O(log W)，总O(n log W)，空间O(W)。空集合初始化O(1)。特点值<2^31，差与累计用long long，再模10^6。

易错点

集合从空恢复时要重新设置类型。lower_bound可能到end或begin，必须处理只有前驱或只有后继的边界。相同距离取较小值，不是后到者。独立答案用排序数组和bisect定位，再直接删除。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, kind = -1;
    cin >> n;
    set<long long> waiting;
    long long answer = 0;
    while (n--) {
        int type;
        long long value;
        cin >> type >> value;
        if (waiting.empty()) {
            kind = type;
            waiting.insert(value);
        } else if (kind == type)
            waiting.insert(value);
        else {
            auto hi = waiting.lower_bound(value), chosen = hi;
            if (hi == waiting.end())
                chosen = prev(hi);
            else if (hi != waiting.begin()) {
                auto lo = prev(hi);
                if (value - *lo <= *hi - value)
                    chosen = lo;
            }
            answer = (answer + llabs(value - *chosen)) % 1000000;
            waiting.erase(chosen);
        }
    }
    cout << answer << '\n';
}