记录编号	56624	评测结果	AAAAAAAAAA
题目名称	[HNOI 2004] 宠物收养所	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.116 s
提交时间	2013-04-01 17:16:59	内存使用	0.31 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<cmath>
using namespace std;
typedef set<int>  SET;
SET pet,owner;
int unsat=0;//不满意总和
void insert(SET &A,int x,SET &B){//x属于A,向B里面匹配
	if(B.size()==0){
		A.insert(x);//B是空,直接向A加
		return;
	}
	SET::iterator now,left;
	int temp,ans;
	now=B.lower_bound(x);//查找第一个>=x的
	if(now==B.end()){//不存在这样的值
		now--;
		ans=abs(*now-x);
		B.erase(now);
		unsat+=ans;
		unsat%=1000000;
		return;
	}
	if(now==B.begin()){//第一个
		ans=abs(*now-x);
		B.erase(now);
		unsat+=ans;
		unsat%=1000000;
		return;
	}
	ans=abs(*now-x);
	left=now,left--;
	temp=abs(*left-x);
	if(temp<=ans){//左边那个更为匹配
		B.erase(left);
		unsat+=temp;
		unsat%=1000000;
		return;
	}
	else{
		B.erase(now);
		unsat+=ans;
		unsat%=1000000;
		return;
	}
}
int main(){
	freopen("pet.in","r",stdin);
	freopen("pet.out","w",stdout);
	pet.clear(),owner.clear();
	int n;
	scanf("%d",&n);
	int a,b,i;
	for(i=0;i<n;i++){
		scanf("%d%d",&a,&b);
		if(!a) insert(pet,b,owner);
		else insert(owner,b,pet);
	}
	printf("%d\n",unsat);
	return 0;
}