首页 > 代码库 > [HNOI2004]宠物收养所
[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;}
[HNOI2004]宠物收养所
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。