一眼查找前驱后继的题。注意到一句话：
那么用set就没有什么阻碍了，方便又快捷。
题意很简单，若宠物多则查找与人需求最接近的上下两个值，人多则找与宠物最接近的上下两个人的值。出题人很善良，把选人和选宠物的标准定成一样的，这样我们只写一个平衡树就可以了。
操作很简单，如果来的人（或宠物）与当前余下的同类就插入set，如果set空了就改变余下的类型并插入，若不同类就进行查找，只用到迭代器set::iterator和lower_bound查找操作。
#includeusingnamespacestd;constintRatio=0;constintmaxx=2147483647;intn,ans,lx;sets;namespaceWisadel{ voidWfind(intx) { set::iteratorl,r; l=--s.lower_bound(x),r=s.lower_bound(x); if(x-*l<=*r-x&&*l!=-maxx)ans+=x-*l,s.erase(l); elseans+=*r-x,s.erase(r); //查找更新答案 ans%=1000000; } shortmain() { scanf("%d",&n); s.insert(-maxx),s.insert(maxx);//防止越界 for(inti=1;i<=n;i++) { inta,b; scanf("%d%d",&a,&b); if(s.size()==2)lx=a,s.insert(b); elseif(lx==a)s.insert(b); elseWfind(b); } printf("%d\n",ans); returnRatio; }}intmain(){returnWisadel::main();}
