[HNOI2004]宠物收养场 一道可以用STLset解决的问题 这题貌似解法很多,但是蒟蒻只会用STL的set… 开两个set,每个分别插入INF与-INF作为边界 每次输入,如果另一个set中有可用元素,则取出进行判断 lower_bound(x)可以找出第一个大于等于x的值的位置,–x即第一个小于x的值 比较b与两数之差即可 当然,也可以只开一个set,以减少代码长度,实现也很简单 实现 一定要记得取模与开long long…
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
| #include <bits/stdc++.h> using namespace std;
int main() { const int INF = 1 << 30; set<int> man, pet; man.insert(INF); man.insert(-INF); pet.insert(INF); pet.insert(-INF); int n, a, b; cin >> n; long long ans = 0; while (n--) { cin >> a >> b; if (a == 0) { if (man.size() != 2) { set<int>::iterator l = --man.lower_bound(b), r = man.lower_bound(b); if (b - *l <= *r - b && *l != -INF) { ans += b - *l; man.erase(l); } else if (*r != INF) { ans += *r - b; man.erase(r); } } else { pet.insert(b); } } else { if (pet.size() != 2) { set<int>::iterator l = --pet.lower_bound(b), r = pet.lower_bound(b); if (b - *l <= *r - b && *l != -INF) { ans += b - *l; pet.erase(l); } else if (*r != INF) { ans += *r - b; pet.erase(r); } } else { man.insert(b); } } } cout << ans % 1000000 << endl; return 0; }
|