明明的随机数

排序 + 去重。

使用 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 << "";
    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 << "";
    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() << "";
    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 << "";
    } while (next_permutation(a + 1, a + n + 1));
    return 0;
}

求第 k 大数（nth_element）

时间复杂度 $O(n)$。

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 算法速查

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