04-数据结构/07-STL实用例子

明明的随机数

排序 + 去重。

使用 sort + unique

#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> a;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    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; i++)
        cout << a[i] << " ";
    return 0;
}

计数排序

const int MAXAI = 1000;
int cnt[MAXAI + 5];

int main()
{
    int n, ans = 0;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        cnt[x]++;
        if (cnt[x] == 1)
            ans++;
    }
    cout << ans << "\n";
    for (int i = 1; i <= MAXAI; i++)
        if (cnt[i] >= 1)
            cout << i << " ";
}

bitset

const int MAXAI = 1000;
bitset<MAXAI + 1> cnt;

int main()
{
    int n;
    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 << " ";
}

合并果子（priority_queue）

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        pq.push(x);
    }
    long long ans = 0;
    while (pq.size() > 1)
    {
        int a = pq.top(); pq.pop();
        int b = pq.top(); pq.pop();
        ans += a + b;
        pq.push(a + b);
    }
    cout << ans;
    return 0;
}

全排列（next_permutation）

int n;
int a[10];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        a[i] = i;
    do
    {
        for (int i = 1; i <= n; i++)
            cout << "    " << a[i];
        cout << "\n";
    } while (next_permutation(a + 1, a + n + 1));
    return 0;
}

求第 k 大数（nth_element）

时间复杂度 [math]\displaystyle{ O(n) }[/math]。

int n, k;
int a[1000005];

int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    nth_element(a + 1, a + k, a + n + 1, greater<int>());
    cout << a[k];
    return 0;
}

STL 算法速查

算法	说明
sort(begin, end)	排序
sort(begin, end, cmp)	自定义排序
stable_sort(begin, end)	稳定排序
unique(begin, end)	去重（需先排序）
lower_bound(begin, end, x)	第一个 [math]\displaystyle{ \ge x }[/math] 的位置
upper_bound(begin, end, x)	第一个 [math]\displaystyle{ > x }[/math] 的位置
binary_search(begin, end, x)	二分查找是否存在
next_permutation(begin, end)	下一个排列
reverse(begin, end)	反转
max_element(begin, end)	最大值位置
min_element(begin, end)	最小值位置
count(begin, end, x)	统计出现次数
fill(begin, end, x)	填充
nth_element(begin, nth, end)	找第 k 大

> 所有区间均为左闭右开 [begin, end)