STL库扫盲——set容器

set是STL的一个关联容器并带有自动排序和去重的功能

Sets are containers that store unique elements following a specific order. ——C++ Reference

set的操作并不复杂，有以下几种

迭代器
begin cbegin	返回指向容器第一个元素的迭代器 (公开成员函数)
end cend	返回指向容器尾端的迭代器 (公开成员函数)
rbegin crbegin	返回指向容器最后元素的逆向迭代器 (公开成员函数)
rend crend	返回指向前端的逆向迭代器 (公开成员函数)
容量
empty	检查容器是否为空 (公开成员函数)
size	返回容纳的元素数 (公开成员函数)
max_size	返回可容纳的最大元素数 (公开成员函数)
修改器
clear	清除内容 (公开成员函数)
insert	插入元素或结点 (C++17 起) (公开成员函数)
emplace (C++11)	原位构造元素 (公开成员函数)
emplace_hint (C++11)	使用提示原位构造元素 (公开成员函数)
erase	擦除元素 (公开成员函数)
swap	交换内容 (公开成员函数)
extract (C++17)	从另一容器释出结点 (公开成员函数)
merge (C++17)	从另一容器接合结点 (公开成员函数)
查找
count	返回匹配特定键的元素数量 (公开成员函数)
find	寻找带有特定键的元素 (公开成员函数)
contains (C++20)	检查容器是否含有带特定关键的元素 (公开成员函数)
equal_range	返回匹配特定键的元素范围 (公开成员函数)
lower_bound	返回指向首个不小于给定键的元素的迭代器 (公开成员函数)
upper_bound	返回指向首个大于给定键的元素的迭代器 (公开成员函数)

我们将通过一个简单的题目来运用以下set

Description

伊凡在纸上写下了一个由 \(n\) 个非负整数组成的序列 \(a_1\) ， \(a_2\) ，…， \(a_n\) 。这个序列保证单调递增。接着，伊凡又在纸上写下了另一个序列 \(2^{a_1}\) ， \(2^{a_2}\) ，…， \(2^{a_3}\) 。现在他想知道，最少要在这个序列中添加多少个形式为 \(2^x\) 的数（x 为非负整数），才能使这个序列所有整数的和为 \(2^{v-1}\) ，其中 \(v\) 为某个非负整数。

Input

(单组输入)

第 1 行包括 1 个正整数 \(n\)（\(1≤n≤1e5)\)

第 2 行包括 \(n\) 个由空格隔开的整数 \(a_1\) ， \(a_2\) ，…， \(a_n\) 。其中，\(0≤a_i ≤2×10^9\)

Analysis

可能有的人看到这个题目会有一瞬间觉得无从下手，但是看到 \(2^x\) ，是不是一下子就能反应到会和二进制有关呢。

简单分析一下， \(2^x\) 的二进制形式是000001000000（打个比方），而 \(2^{v-1}\) 的形式也是非常有特点00001111111111（打个比方），而想要得到这样的形式我们可以简单地理解成将空填满，需要补的 \(2^x\) 正是填满他们的“原料”。

如果拆烂了来说就是我们输入的\(n\)个数各自填满了所在的位置，我们需要给出从最大的那个数到\(0\)之间有多少个\(0\)没被填充即可。

有的人可能会第一反应想到map，利用map去像处理一个二进制数一样去处理，最后遍历得到0的个数，这么做当然可以，只是时空复杂度相比我们这种做法不占优势。而且浪费了一个非常好的性质，他是有序输入的！

我们先把题目放宽一些，改成序列严格单调增加，我们会得到一个有趣的性质，各个 \(2^x\) 之间并没有必然的联系，也就是说我们输入到第\(k\)位的时候其实前\(k-1\)位都具体的确定了下来，而 \(2^k\) 与 \(2^{k-1}\) 之间的位置则全部是0。这就非常好了，我们就可以在\(O(n)\)的时间内完成这项查找。

然而这个题目多了一点就是输入数据会有相同的点。而这种情况我们则恰恰可以利用set的去重性质去处理，两个 \(2^k\) 相加我们就会得到一个 \(2^{k+1}\) 。如此一来，代码便顺理成章了。

Accepted Code

/*
 * @Author: Gehrychiang
 * @Date: 2020-02-17 11:31:26
 * @Website: www.yilantingfeng.site
 * @E-mail: gehrychiang@aliyun.com
 */
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
set<int> s;
int main()
{
    //freopen("tmpdata.out", "r", stdin);
    //freopen("","w",stdout);
    int n;
    scanf("%d", &n);
    int cnt = 0;
    int las = -1;//由于0位起始所以las的初始值要设为0-1
    int tmp = 0;
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &tmp);
        while (s.count(tmp))//做等效的加法来过滤相同元素
        {
            s.erase(tmp);
            tmp++;
        }
        s.insert(tmp);
    }
    for (set<int>::iterator iter = s.begin(); iter != s.end(); iter++)//预处理完成，开始遍历操作
    {
        cnt += (*iter - las - 1);
        las = *iter;
    }
    printf("%d",cnt);
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}