★★★ 输入文件：pet.in 输出文件：pet.out 简单对比
时间限制：1 s 内存限制：128 MB
最近，阿Q开了一间宠物收养所。收养所提供两种服务：收养被主人遗弃的宠物和让新的主人领养这些宠物。每个领养者都希望领养到自己满意的宠物，阿Q根据领养者的要求通过他自己发明的一个特殊的公式，得出该领养者希望领养的宠物的特点值a（a是一个正整数，a<2^31），而他也给每个处在收养所的宠物一个特点值。这样他就能够很方便的处理整个领养宠物的过程了，宠物收养所总是会有两种情况发生：被遗弃的宠物过多或者是想要收养宠物的人太多，而宠物太少。
|
5
0 2
0 4
1 3
1 2
1 5
|
| 3 |
1 #include <algorithm> 2 #include <iostream> 3 #include <cstring> 4 #include <cstdio> 5 #include <set> 6 using namespace std; 7 set<int>q; 8 int main(){ 9 freopen("pet.in","r",stdin); 10 freopen("pet.out","w",stdout); 11 int n,a,p,ans=0,flag=-1; 12 scanf("%d",&n); 13 for(int i=1;i<=n;i++){ 14 scanf("%d%d",&p,&a); 15 if(flag==-1){ 16 q.insert(a); 17 flag=p; 18 } 19 else if(flag==p) 20 q.insert(a); 21 22 else{ 23 set<int>::iterator l,r,tmp; 24 r=q.lower_bound(a); 25 if(r==q.end()){ 26 r--; 27 ans=(ans+a-*r)%1000000; 28 q.erase(r); 29 } 30 else if(r==q.begin()){ 31 ans=(ans+*r-a)%1000000; 32 q.erase(r); 33 } 34 else{ 35 tmp=r;l=--tmp; 36 if(*r-a<a-*l){ 37 ans=(ans+*r-a)%1000000; 38 q.erase(r); 39 } 40 else{ 41 ans=(ans+a-*l)%1000000; 42 q.erase(l); 43 } 44 } 45 if(q.size()==0) 46 flag=-1; 47 } 48 49 } 50 printf("%d\n",ans); 51 }
数据结构(set)：COGS 62. [HNOI2004] 宠物收养所
原文：http://www.cnblogs.com/TenderRun/p/5341537.html