题解 P2286 【[HNOI2004]宠物收养场】

· · 题解

题意简化：

每个宠物的特征值 a，每个收养者希望收养的宠物的特征值 b。

收养者：在所有宠物中找距离 b 最近的 a。

宠物： 在所有收养者中找距离 a 最近的 b。

不满意度：收养到宠物的 |a-b|。

解题思路：

需要标记 set 中的是宠物还是收养者。

接下来输入的数据：

如果类型相同，进入 set；

如果类型不同，找收养关系，出 set。

范例代码：

#include <bits/stdc++.h>
using namespace std;
int read()
{
    int 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;
}
const int MAXN = 800008, INF = 0x3f3f3f3f, MOD = 1000000;
set<int> se; set<int>::iterator it;
int ans, a, val, op,opin=-1, mina, n;
int main()
{
    n = read();
    opin = -1;
    for(int i = 1; i<=n; i++)
    {
        op = read(); a = read();
        if(opin==-1 || op==opin)
        {
            se.insert(a);
            opin = op;
        }
        else
        {
            mina = INF;
            //lower
            it = se.lower_bound(a);
            if(it!=se.begin()) {it--; val = *it; mina = a-*it;}
            //upper
            it = se.upper_bound(a);
            if(it!=se.end())
            {
                if(mina > (*it-a))
                {
                      val = *it;
                      mina = *it-a;
                }
            }
            ans += mina;
            ans %= MOD;
            se.erase(val);
            if(se.empty()) opin = -1;
        }
    //测试：cout << "set: "; for(it = se.begin(); it!=se.end(); it++) cout << *it << " " ; cout <<endl;
    }
    printf("%d\n",ans);
    return 0;

}