[HNOI2004]宠物收养所

题目大意

收养所中每个宠物的值是a，领养者的期望是b，领养者将会领养一只目前未被领养的宠物中特点值最接近a的一只宠物。

（任何两只宠物的特点值都不可能是相同的，任何两个领养者的希望领养宠物的特点值也不可能是一样的）。

当出现 a-b == a+b时，优先选择a-b。 最终求的是每个领养者的 abs(a-b)的值 取模100000.

初始时宠物和领养者数量都为0，依次按照先后顺序出现。 即有先后顺序

思考

题目的导向是 让a、b的差值尽量小，那么对于每个a 我们找到一个合适的b即可，这里最合适的方法就是二分，对于每个a 二分找出一个b的值。 对于b也同样。

所以可以功能 两个set维护 宠物集合 和 领养者集合 来实现，对于每个a ，我们在b中二分找出 >=a的位置，并取它的前一位（因为a-b优先选择）

再考虑一下 a b 空集合的特殊情况就可以AC了。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <set>
#include <iostream>
using namespace std;
set<int> pet,owner;
int n,ans;

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

inline int add(int x,int y){
    ans = (ans + ( diff(x,y) % 1000000 ) ) %1000000;
}
void solve(set<int> &set,int x){
if(set.size()==1){
        add(x,*set.begin());
set.clear();
    }
else{
        std::set<int>::const_iterator r = set.lower_bound(x);
if(r==set.begin()){
            add(x,*r);
set.erase(r);
        }
else{
            std::set<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(){
    scanf("%d",&n);
while(n--){
int x,y;
        scanf("%d%d",&x,&y);
if(x==0){
if( owner.empty() ){
                pet.insert(y);
            }
else{
                solve(owner,y);
            }
        }
if(x==1){
if( pet.empty() ){
                owner.insert(y);
            }
else{
                solve(pet,y);
            }
        }
    }    
    printf("%d\n",ans);
return 0;
}