33DAI：导入1个版本

2026-05-20T18:12:10Z

导入1个版本

←上一版本		2026年5月20日 (三) 18:12的版本
（没有差异）

->Importer：批量导入三三文档

2026-05-20T16:50:33Z

批量导入三三文档

←上一版本		2026年5月20日 (三) 16:50的版本
（没有差异）

33DAI：导入1个版本

2026-05-20T16:25:29Z

导入1个版本

←上一版本		2026年5月20日 (三) 16:25的版本
（没有差异）

->Importer：批量导入三三文档

2026-05-20T16:22:29Z

批量导入三三文档

新页面

== 明明的随机数 ==

排序 + 去重。

=== 使用 <code>sort</code> + <code>unique</code> ===

<syntaxhighlight lang="cpp">
#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;
}
</syntaxhighlight>

=== 计数排序 ===

<syntaxhighlight lang="cpp">
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 << " ";
}
</syntaxhighlight>

=== bitset ===

<syntaxhighlight lang="cpp">
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 << " ";
}
</syntaxhighlight>

== 合并果子（priority_queue） ==

<syntaxhighlight lang="cpp">
#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;
}
</syntaxhighlight>

== 全排列（<code>next_permutation</code>） ==

<syntaxhighlight lang="cpp">
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;
}
</syntaxhighlight>

== 求第 k 大数（<code>nth_element</code>） ==

时间复杂度 <math>O(n)</math>。

<syntaxhighlight lang="cpp">
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;
}
</syntaxhighlight>

== STL 算法速查 ==

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

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

[[Category:数据结构]]
[[Category:三三文档]]

04-数据结构/07-STL实用例子 - 版本历史

33DAI：​导入1个版本

->Importer：​批量导入三三文档

33DAI：​导入1个版本

->Importer：​批量导入三三文档

33DAI：导入1个版本

->Importer：批量导入三三文档

33DAI：导入1个版本

->Importer：批量导入三三文档