[HNOI2004]宠物收养场 题解 set
题目链接：https://www.luogu.com.cn/problem/P2286
题目大意：
有 N(N≤80000)" role="presentation">N(N≤80000) 只宠物或领养者依次来到宠物收养场，他们都有一个特征值。
当有一只宠物进入收养场时，如果存在等待的领养者，会从领养者中挑选和宠物特征值最接近的领养者匹配（然后离开收养场）；否则，宠物等待。
当有一个领养者进入收养场时，如果存在等待的宠物，会从宠物中挑选和领养者特征值最接近的宠物匹配（然后离开收养场）；否则，领养者等待。
每次匹配，答案都会加上匹配的宠物和领养者的差的绝对值，求答案。
解题思路：
首先这种边界性问题考虑用二分解决。
但是数据是动态的（动态插入和删除），所以考虑用集合（set）来维护数据，然后在set上进行二分。
实现代码如下：
#include <bits/stdc++.h> using namespace std; const int maxn = 80080, MOD = 1000000; set<int> pets, owners; int n, ans, op, a; void solve(set<int> &st, int a) { if (st.size() == 1) { ans = (ans + abs(a - (*st.begin()))) % MOD; st.clear(); } else { set<int>::iterator r = st.lower_bound(a); if (r == st.begin()) { ans = (ans + abs(a - (*st.begin()))) % MOD; st.erase(r); } else { set<int>::iterator l = --st.lower_bound(a); if (r == st.end() || abs(a - *l) <= abs(a - *r)) { ans = (ans + abs(a - (*l))) % MOD; st.erase(l); } else { ans = (ans + abs(a - (*r))) % MOD; st.erase(r); } } } } int main() { scanf("%d", &n); while (n --) { scanf("%d%d", &op, &a); if (op == 0) { if (owners.size() == 0) pets.insert(a); else solve(owners, a); } else { if (pets.size() == 0) owners.insert(a); else solve(pets, a); } } printf("%dn", ans); return 0; }
相关知识
[HNOI2004]宠物收养场 题解 set
上海唯一正规的“宠物救助组织”竟是场骗局！
所谓“最大宠物救助组织”利用爱心设骗局:送养收养都收费
时尚宠物狗狗连衣帽卫衣设计展示样机素材 Dog Suits Mockup
大兴清城宠物火化场地址
丽水宠物火化场：为宠物送别的安详守护地
徐州90后夫妻收养流浪猫狗开“猫咖”“狗咖”：“让它们‘打工’养活自己”
密码 pasuwado题解
宁波有宠物救助站吗？我捡到一只小猫，不过自己不会养，不知道有没有专门收养流浪动物的地方
寻找广州市内残疾宠物救助中心（了解关于残疾动物收养的相关信息）
网址: [HNOI2004]宠物收养场 题解 set https://m.mcbbbk.com/newsview28120.html
| 上一篇: 宠物医疗行业面临人才缺口，「知宠 |
下一篇: 梦幻西游手游 宠物最强克星 夜叉 |
