Hunter'sBlog

这道题目可以算是一道set的板子题（在CJC大佬的提醒下恍然大悟，CJC的博客），于是这篇题解某种意义上其实是对于set的讲解和复习。关于STL的话，全称为Standard Template Library，说白了就是一个非常多功能的库，引用时按情况引用，可能会有set map algorithm等等，按情况来分析，用途很多，有封装好的快排、大根小根堆（优先队列）、二分查找、全排列、各种神仙玩意儿。set则是其中的一个工具。

Set

set和multiset的区别是，后者可以有重复的元素，前者不可以。
set插入重复元素可能会不成功，所以有重复元素要用multiset。
用法：

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
#include <iostream>
#include <cstdio>
#include <set> //set所在的库

using namespace std;

int main()
{
    set<int> st; //定义方法，其他类型类似
    int a[10] = {1, 2, 3, 8, 7, 7, 5, 6, 8, 12};
    for (int i = 1; i < 10; ++i)
        st.insert(a[i]);//插入方式
    cout << st.size() << endl; //st.size()返回这个set的大小，整形
    set<int>::iterator i; //迭代器，类似于一个指向set中某个元素的指针，不可以比较大小，不可以相加相减，但可以++i（迭代）
    for (i = st.begin(); i != st.snd(); ++i) //由于迭代器的特殊性，只能用这种方式进行循环
        cout << * i << ","; 
    cout endl;
    pair<set<int>::iterator, bool> result = st.insert(2);
    if (!result.second)
        cout << * result.first << " already exists." << endl;
    else
        cout << * result.first << " inserted." << endl;

    return 0;
}

更多的关于set的用法和函数详解，可以访问C++ reference

这道题目

题目简述：
凡凡开了一间宠物收养场。收养场提供两种服务：收养被主人遗弃的宠物和让新的主人领养这些宠物。

每个领养者都希望领养到自己满意的宠物，凡凡根据领养者的要求通过他自己发明的一个特殊的公式，得出该领养者希望领养的宠物的特点值$a$（$a$是一个正整数，$a<2^{31}$），而他也给每个处在收养场的宠物一个特点值。这样他就能够很方便的处理整个领养宠物的过程了，宠物收养场总是会有两种情况发生：被遗弃的宠物过多或者是想要收养宠物的人太多，而宠物太少。

被遗弃的宠物过多时，假若到来一个领养者，这个领养者希望领养的宠物的特点值为$a$，那么它将会领养一只目前未被领养的宠物中特点值最接近$a$的一只宠物。（任何两只宠物的特点值都不可能是相同的，任何两个领养者的希望领养宠物的特点值也不可能是一样的）如果有两只满足要求的宠物，即存在两只宠物他们的特点值分别为$a-b$和$a+b$，那么领养者将会领养特点值为$a-b$的那只宠物。

收养宠物的人过多，假若到来一只被收养的宠物，那么哪个领养者能够领养它呢？能够领养它的领养者，是那个希望被领养宠物的特点值最接近该宠物特点值的领养者，如果该宠物的特点值为$a$，存在两个领养者他们希望领养宠物的特点值分别为$a-b$和$a+b$，那么特点值为$a-b$的那个领养者将成功领养该宠物。

一个领养者领养了一个特点值为$a$的宠物，而它本身希望领养的宠物的特点值为$b$，那么这个领养者的不满意程度为$abs(a-b)$。

你得到了一年当中，领养者和被收养宠物到来收养所的情况，请你计算所有收养了宠物的领养者的不满意程度的总和。这一年初始时，收养所里面既没有宠物，也没有领养者。

问题解决：

知道了set怎么用，辣么就好办了（好像还要知道一个lower_bound()）

我们只要把每次宠物的编号插入，然后直接查询，查询的话也是用STL中的lower_bound和uper_bound，然后这道题目就可以A了

代码如下

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

#include <bits/stdc++.h> //万能头文件

using namespace std;

const int MAXN = 1000010;
const int MAX_INT = 1e9;

int n, ans;
set<int> s; //定义set

void find(int x) 
{
    set<int>::iterator left, right;//定义迭代器
    left = --s.lower_bound(x);
    right = s.lower_bound(x);
    if (x - *left <= *right - x && *left != -MAX_INT)
    {
        ans += x - *left;
        s.erase(left);
    } else {
        ans += *right - x;
        s.erase(right);
    }
    ans %= 1000000;
}

int main()
{
    scanf("%d", &n);
    int hod;
    s.insert(-MAX_INT), s.insert(MAX_INT); //通过插入最大整型和最小整型来防止查找溢出，这是一位大佬的方法，非常秒！！
    for (int i = 1; i <= n; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        if (s.size() == 2)
        {
            hod = a;
            s.insert(b);
        } else 
            if (a == hod) 
                s.insert(b); else find(b);
    }
    printf("%d\n", ans);
    return 0;
}

完事儿~
考虑在写一个关于STL的整合，这一切都要从一只🦇说起……

评论