HNOI2004宠物收养场

发表于 更新于 分类于 阅读次数：

[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;
}