STL例子

• STL容器库常用内容

明明的随机数

排序后枚举

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000000;
const int MAXAI = 100000;
int n;
int a[MAXN + 5];
void work()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    sort(a + 1, a + n + 1);
    int cnt = 1;
    for (int i = 2; i <= n; i++)
        if (a[i] != a[i - 1])
            cnt++;
    cout << cnt << "\n";
    cout << a[1] << " ";
    for (int i = 2; i <= n; i++)
        if (a[i] != a[i - 1])
            cout << a[i] << " ";
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    work();
    return 0;
}

使用 unique 去重

int n;
int a[MAXN + 5];
void work()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    sort(a + 1, a + n + 1);
    int nn = unique(a + 1, a + n + 1) - a - 1;
    cout << nn << "\n";
    for (int i = 1; i <= nn; i++)
        cout << a[i] << " ";
}

vector 排序后 unique 去重

int n;
vector<int> a;
void work()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        a.push_back(x);
    }
    sort(a.begin(), a.end());
    int nn = unique(a.begin(), a.end()) - a.begin();
    cout << nn << "\n";
    for (int i = 0; i <= nn - 1; i++)
        cout << a[i] << " ";
}

vector 排序后迭代器枚举

int n;
vector<int> a;
void work()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        a.push_back(x);
    }
    sort(a.begin(), a.end());
    // [a.begin(), R)
    vector<int>::iterator R = unique(a.begin(), a.end());
    cout << (R - a.begin()) << "\n";
    for (auto it = a.begin(); it != R; it++)
        cout << (*it) << " ";
}

计数排序

int n;
int a[MAXN + 5];
int cnt[MAXAI + 5];
void work()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
        
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        cnt[a[i]]++;
        if (cnt[a[i]] == 1)
            ans++;
    }
    cout << ans << "\n";
    for (int i = 1; i <= MAXAI; i++)
        if (cnt[i] >= 1)
            cout << i << " ";
}

bitset 判断每个数是否出现

int n;
bitset<MAXAI + 1> cnt;
void work()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        cnt.set(x);
    }
    cout << cnt.count() << "\n";
    for (int i = 1; i <= MAXAI; i++)
        if (cnt[i])
            cout << i << " ";
}

合并果子

multiset

#include <bits/stdc++.h>
using namespace std;
int n;
int a[30000 + 5];
multiset<int> s;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        s.insert(a[i]);
    }
    long long ans = 0;
    while (s.size() > 1)
    {
        int a = *s.begin();
        // 如果erase(a)，会删除所有 a，所以只删除迭代器的值
        s.erase(s.begin());
        int b = *s.begin();
        s.erase(s.begin());
        ans += (a + b);
        s.insert(a + b);
    }
    cout << ans;
    return 0;
}

map

#include <bits/stdc++.h>
using namespace std;
int n;
int a[30000 + 5];
map<int, int> m;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        m[a[i]]++;
    }
    long long ans = 0;
    for (int i = 1; i <= n - 1; i++)
    {
        auto it = m.begin();
        // 取 a
        int a = (*it).first;
        (*it).second--;
        if ((*it).second == 0)
            m.erase(it);
        // 取 b
        it = m.begin();
        int b = it->first;
        it->second--;
        if (it->second == 0)
            m.erase(it);
        // 合并
        ans += (a + b);
        m[a + b]++;
    }
    cout << ans;
    return 0;
}

priority_queue

传相反数实现小根堆

#include <bits/stdc++.h>
using namespace std;
int n;
int a[30000 + 5];
// q.push(x); // 把 x 放入优先队列（O(logSize)）
// q.top();   // 优先队列中最大的元素（O(1)）
// q.pop();   // 弹出（删除）最大的元素（O(logSize)）
priority_queue<int> q;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    // 都放到优先队列里
    for (int i = 1; i <= n; i++)
        q.push(-a[i]); // 存相反数，来实现最小堆
    int ans = 0;
    for (int i = 1; i <= n - 1; i++)
    {
        int x = -q.top();
        q.pop();
        int y = -q.top();
        q.pop();
        ans += x + y;
        q.push(-(x + y));
    }
    cout << ans;
    return 0;
}

重载运算符的优先队列

#include <bits/stdc++.h>
using namespace std;
int n;
struct Guozi
{
    int daxiao;
};
Guozi a[30000 + 5];
// 把小于号用大于的规则定义，这样取出来的最大值就会使daxiao最小的
bool operator<(const Guozi &a, const Guozi &b)
{
    return a.daxiao > b.daxiao;
}
// q.push(x); // 把 x 放入优先队列（O(logSize)）
// q.top();   // 优先队列中最大的元素（O(1)）
// q.pop();   // 弹出（删除）最大的元素（O(logSize)）
priority_queue<Guozi> q;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i].daxiao;
    // 都放到优先队列里
    for (int i = 1; i <= n; i++)
        q.push(a[i]);
    int ans = 0;
    for (int i = 1; i <= n - 1; i++)
    {
        int x = q.top().daxiao;
        q.pop();
        int y = q.top().daxiao;
        q.pop();
        ans += x + y;
        q.push((Guozi){x + y});
    }
    cout << ans;
    return 0;
}

自己实现小根堆

#include <bits/stdc++.h>
using namespace std;
int n;
const int MAXN = 30000;
// 小根堆（越小越优先的优先队列）
struct PQ
{
    int tot;
    int t[MAXN + 5];
    void clear()
    {
        tot = 0;
    }
    int size()
    {
        return tot;
    }
    bool empty()
    {
        return tot == 0;
    }
    int top()
    {
        // 可以自己检测非法
        return t[1];
    }
    void push(int x)
    {
        tot++;
        t[tot] = x;
        int now = tot;
        // 不是根节点，并且父节点比自己大的时候往上走
        while (now != 1 && t[now / 2] > t[now])
        {
            swap(t[now / 2], t[now]);
            now /= 2;
        }
    }
    void pop()
    {
        swap(t[1], t[tot]);
        tot--;
        // 从根节点开始维护到合适位置
        int now = 1;
        while (1)
        {
            // 没有子节点
            if (now * 2 > tot)
                break;
            // 只有左子节点
            else if (now * 2 + 1 > tot)
            {
                if (t[now * 2] < t[now])
                {
                    swap(t[now * 2], t[now]);
                    now = now * 2;
                }
                else
                    break;
            }
            // 左右子节点都有
            else
            {
                // 自己最小
                if (t[now] <= t[now * 2] && t[now] <= t[now * 2 + 1])
                    break;
                // 左边最小
                else if (t[now * 2] <= t[now * 2 + 1])
                {
                    swap(t[now * 2], t[now]);
                    now = now * 2;
                }
                else
                {
                    swap(t[now * 2 + 1], t[now]);
                    now = now * 2 + 1;
                }
            }
        }
    }
};
PQ q;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    q.clear();
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        q.push(x);
    }
    long long ans = 0;
    while (q.size() > 1)
    {
        int a = q.top();
        q.pop();
        int b = q.top();
        q.pop();
        // 合并
        ans += (a + b);
        q.push(a + b);
    }
    cout << ans;
    return 0;
}

全排列问题

next_permutation

如果已经是最后一个排列了，执行之后会变为第一个排列，并返回假，否则返回真。

#include <bits/stdc++.h>
using namespace std;
int n;
int a[10];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        a[i] = i;
    while (1)
    {
        for (int i = 1; i <= n; i++)
            cout << "    " << a[i];
        cout << "\n";
        if (!next_permutation(a + 1, a + n + 1))
            break;
    }
    return 0;
}

求第 k 大数

nth_element

时间复杂度 [math]\displaystyle{ O(n) }[/math]，快排每次只排序 k 所在的那一部分。

#include <bits/stdc++.h>
using namespace std;
int n, k;
int a[1000000 + 5];
bool cmp(int a, int b)
{
    return a > b;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    nth_element(a + 1, a + k, a + n + 1, cmp);
    cout << a[k];
    return 0;
}