STL库扫盲——set容器

STL库扫盲——set容器

/ 5评 / 2264次 / 6

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

《“STL库扫盲——set容器”》 有 5 条评论

  1. 马家沟老三说道:

    站主小哥哥,tql

  2. 雷泽诺夫说道:

    扫盲扫盲,越扫越盲

  3. jsc说道:

    站主小gg可撩

  4. JWmm说道:

    还是没我牛逼

  5. 云茹说道:

    小哥哥单身嘛?

发表回复

您的电子邮箱地址不会被公开。

你好 No.59611