#include <bits/stdc++.h> // 竞赛一把梭
// 或精确包含:
#include <algorithm>
#include <numeric> // accumulate / iota / partial_sum
#include <functional> // greater<>cpp一、排序家族#
1. sort:快速排序变体(introsort)#
vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};
sort(v.begin(), v.end()); // 升序:1 1 2 3 4 5 6 9
sort(v.begin(), v.end(), greater<int>()); // 降序
sort(v.begin(), v.begin() + 4); // 只排前 4 个
// 数组也直接用指针
int a[100];
sort(a, a + n);
sort(a + 1, a + 1 + n); // 1-indexed 数组排序cpp复杂度 O(n log n),不稳定(相等元素的相对顺序可能改变)。
2. 自定义比较器(竞赛核心技能)#
// 结构体按多关键字排序
struct Node { int a, b; };
vector<Node> v;
sort(v.begin(), v.end(), [](const Node& x, const Node& y) {
if (x.a != y.a) return x.a < y.a; // a 升序
return x.b > y.b; // a 相同则 b 降序
});
// pair 默认字典序,通常直接 sort 即可
vector<pair<int,int>> p;
sort(p.begin(), p.end()); // 先 first 后 secondcpp比较器必须满足严格弱序:
- 用
<或>,不能用<=/>=(违反”自己不大于自己”,导致未定义行为甚至崩溃); - 不能比较过程中修改元素;
- lambda 按 const 引用传参,避免拷贝。
3. stable_sort:稳定排序#
stable_sort(v.begin(), v.end(), cmp);cpp相等元素保持原相对顺序,复杂度 O(n log² n)(通常借助额外内存做到 O(n log n))。需要”排序不打乱原顺序”时使用,如先按第二关键字排、再稳定排序第一关键字,可实现多关键字排序。
4. partial_sort:只排前 k 个#
// 使前 k 个元素成为全数组中最小的 k 个且有序,其余位置不保证
partial_sort(v.begin(), v.begin() + k, v.end());cpp复杂度 O(n log k)。求”最小的 k 个且要有序”时比全排划算。
5. nth_element:第 k 小(快速选择)#
// 使 v[k] 成为排序后应在的元素;左侧都 <= 它,右侧都 >= 它,两侧各自无序
nth_element(v.begin(), v.begin() + k, v.end()); // k 是 0-based
int kth = v[k];cpp平均 O(n)。求中位数、第 k 小、分治划分时非常有用:
nth_element(v.begin(), v.begin() + v.size()/2, v.end());
int median = v[v.size()/2];cpp6. 排序相关检查#
bool ok = is_sorted(v.begin(), v.end()); // 是否已升序
auto it = is_sorted_until(v.begin(), v.end()); // 第一个破坏升序的位置cpp二、二分查找家族(必须先有序!)#
在升序区间上(默认 < 比较):
vector<int> v = {1, 2, 4, 4, 4, 7, 9};
auto lo = lower_bound(v.begin(), v.end(), 4); // 第一个 >= 4 → 下标 2
auto hi = upper_bound(v.begin(), v.end(), 4); // 第一个 > 4 → 下标 5
bool exists = binary_search(v.begin(), v.end(), 4); // 只返回 bool
auto [l, r] = equal_range(v.begin(), v.end(), 4); // [lo, hi) 对
// 转下标 / 统计个数
int pos = lo - v.begin(); // 2
int cnt = hi - lo; // 3,即 4 的出现次数
// 判断存在性(lower_bound 可能返回 end,必须检查)
bool found = lo != v.end() && *lo == 4;cpp竞赛四大标准问题#
// 1. 第一个 >= x
int p1 = lower_bound(v.begin(), v.end(), x) - v.begin();
// 2. 第一个 > x
int p2 = upper_bound(v.begin(), v.end(), x) - v.begin();
// 3. 最后一个 < x(严格前驱)
auto it = lower_bound(v.begin(), v.end(), x);
if (it != v.begin()) { --it; /* *it < x */ }
// 4. x 的插入位置(保持有序)
v.insert(lower_bound(v.begin(), v.end(), x), x);cpp自定义比较器下的语义反转#
// 降序数组必须配 greater<>,且 lower_bound 语义变为"第一个 <= x"
sort(v.begin(), v.end(), greater<int>());
auto it = lower_bound(v.begin(), v.end(), x, greater<int>());cpp注意:比较器与排序规则必须一致,否则结果无意义。
手写二分 vs 库函数#
库函数二分处理的是”在已排序序列中找位置”;如果答案是”二分答案法”(对答案值域二分),仍需手写:
int lo = 0, hi = 1e9;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (check(mid)) hi = mid;
else lo = mid + 1;
}cpp三、去重与删除惯用法(超高频)#
1. unique + erase:排序去重#
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());cppunique 只把相邻重复元素移到尾部并返回新逻辑尾,不改变容器大小。全局去重必须先 sort。
2. remove / remove_if + erase:删除指定元素#
v.erase(remove(v.begin(), v.end(), x), v.end()); // 删所有 x
v.erase(remove_if(v.begin(), v.end(), [](int t) {
return t % 2 == 0;
}), v.end()); // 删所有偶数cppremove 同样不改变容器大小,只是把保留元素前移。复杂度 O(n),比循环 erase(O(n²))好得多。
3. 离散化完整模板#
vector<int> a(n);
for (auto &x : a) cin >> x;
vector<int> b = a;
sort(b.begin(), b.end());
b.erase(unique(b.begin(), b.end()), b.end());
for (auto &x : a)
x = lower_bound(b.begin(), b.end(), x) - b.begin() + 1; // 1-based 离散值cpp四、查找与统计#
vector<int> v = {1, 2, 3, 2, 4};
auto it = find(v.begin(), v.end(), 3); // 线性查找,O(n)
bool has = it != v.end();
auto it2 = find_if(v.begin(), v.end(), [](int x) { return x > 2; });
int c = count(v.begin(), v.end(), 2); // 2
int c2 = count_if(v.begin(), v.end(), [](int x) { return x % 2 == 0; });
// C++17 条件判断三件套
bool a1 = all_of(v.begin(), v.end(), [](int x) { return x > 0; });
bool a2 = any_of(v.begin(), v.end(), [](int x) { return x == 4; });
bool a3 = none_of(v.begin(), v.end(), [](int x) { return x < 0; });cpp无序 vector 里 find 是 O(n);要 O(log n) 请排序后二分或用 set。
五、最值#
// 多值最值
int x = min(a, b);
int y = max({3, 1, 4, 1, 5}); // 初始化列表版本,C++11
auto [mn, mx] = minmax(a, b); // C++14,同时返回
// 区间最值:返回迭代器
auto it = min_element(v.begin(), v.end());
auto jt = max_element(v.begin(), v.end());
int mn = *it; // 空区间不能解引用!
int pos = jt - v.begin(); // 最值下标
auto [it1, it2] = minmax_element(v.begin(), v.end()); // 一次遍历
// C++17 clamp:把值限制在 [lo, hi]
int t = clamp(x, 0, 100);cpp六、变形操作#
vector<int> v = {1, 2, 3, 4, 5};
reverse(v.begin(), v.end()); // 5 4 3 2 1
reverse(v.begin() + 1, v.begin() + 4); // 局部反转
// rotate:左旋转,mid 处的元素转到开头
rotate(v.begin(), v.begin() + 2, v.end()); // 3 4 5 1 2
// 随机打乱(配合 <random>)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
shuffle(v.begin(), v.end(), rng); // random_shuffle 已在 C++17 移除,别用
// 交换
swap(a, b); // 两变量
iter_swap(v.begin(), v.begin() + 3); // 两迭代器指向的元素cpprotate 常用于循环位移、把某段移到开头。
七、填充与生成#
vector<int> v(10);
fill(v.begin(), v.end(), -1); // 全填 -1
fill_n(v.begin(), 5, 0); // 前 5 个填 0
// iota:连续递增填充(<numeric>)
iota(v.begin(), v.end(), 1); // 1 2 3 ... 10
// generate:用函数生成
int cur = 0;
generate(v.begin(), v.end(), [&] { return cur += 2; }); // 2 4 6 ...
// 初始化前缀下标数组(排序下标时常用)
vector<int> idx(n);
iota(idx.begin(), idx.end(), 0);
sort(idx.begin(), idx.end(), [&](int i, int j) { return a[i] < a[j]; });cppiota + sort 的”下标排序”是保留原位置信息的经典技巧。
八、数值算法(<numeric>)#
vector<int> v = {1, 2, 3, 4, 5};
// 求和:初始值类型决定累加类型!
long long sum = accumulate(v.begin(), v.end(), 0LL); // 0LL 防溢出
// 写成 0 则按 int 累加,大数会溢出
// 前缀和
vector<int> pre(v.size());
partial_sum(v.begin(), v.end(), pre.begin()); // 1 3 6 10 15
// 相邻差分
vector<int> dif(v.size());
adjacent_difference(v.begin(), v.end(), dif.begin()); // 1 1 1 1 1
// 内积
long long dot = inner_product(v.begin(), v.end(), v.begin(), 0LL);
// gcd / lcm(C++17,<numeric>)
int g = gcd(12, 18); // 6
int l = lcm(4, 6); // 12cpp九、全排列(枚举神器)#
vector<int> v = {1, 2, 3};
// 要求从升序开始才能枚举全所有排列
sort(v.begin(), v.end());
do {
// 处理当前排列:1 2 3 → 1 3 2 → 2 1 3 → ...
} while (next_permutation(v.begin(), v.end()));
// prev_permutation:从降序开始反向枚举cppnext_permutation按字典序生成下一个排列,已是最后一个时返回false并重置为升序;- 枚举
n!种排列,n <= 10左右可接受(10! ≈ 362 万); - 比手写 DFS 全排列简洁,且可直接对带重复元素的序列去重枚举。
十、堆算法(vector 当堆用)#
vector<int> h = {3, 1, 4, 1, 5};
make_heap(h.begin(), h.end()); // O(n) 建大根堆
h.push_back(9);
push_heap(h.begin(), h.end()); // 新元素入堆 O(log n)
pop_heap(h.begin(), h.end()); // 堆顶移到末尾 O(log n)
int mx = h.back();
h.pop_back(); // 真正删除
sort_heap(h.begin(), h.end()); // 堆排序,得到升序数组cpp竞赛中多数场景直接用 priority_queue 更方便;堆算法的优势是能遍历整个堆、能排序整个数组。
十一、有序集合运算(归并思想)#
两个已排序序列之间的运算,全部 O(n + m):
vector<int> a = {1, 2, 4, 7}, b = {2, 4, 5};
vector<int> c;
c.resize(a.size() + b.size());
auto it = set_union(a.begin(), a.end(), b.begin(), b.end(), c.begin());
c.resize(it - c.begin()); // 并集:1 2 4 5 7
c.resize(max(a.size(), b.size()));
it = set_intersection(a.begin(), a.end(), b.begin(), b.end(), c.begin());
c.resize(it - c.begin()); // 交集:2 4
it = set_difference(a.begin(), a.end(), b.begin(), b.end(), c.begin());
c.resize(it - c.begin()); // 差集 a - b:1 7
// merge:归并两个有序序列为一个有序序列
merge(a.begin(), a.end(), b.begin(), b.end(), c.begin());cpp竞赛中手写双指针也很常见,库函数版更不易写错。
十二、拷贝与遍历#
// copy:区间拷贝到另一容器
vector<int> b(v.size());
copy(v.begin(), v.end(), b.begin());
// copy_if:按条件拷贝(C++11)
copy_if(v.begin(), v.end(), back_inserter(b), [](int x) { return x > 0; });
// move:移动元素而非拷贝(大对象加速)
vector<string> dst(src.size());
move(src.begin(), src.end(), dst.begin());
// transform:映射变换
transform(v.begin(), v.end(), v.begin(), [](int x) { return x * x; });
// for_each(多数场景直接写范围 for 更直观)
for_each(v.begin(), v.end(), [](int &x) { x *= 2; });cpp十三、复杂度速查表#
| 算法 | 复杂度 | 前提 |
|---|---|---|
sort |
O(n log n) |
无 |
stable_sort |
O(n log n)~O(n log²n) |
无 |
partial_sort |
O(n log k) |
无 |
nth_element |
平均 O(n) |
无 |
lower_bound / upper_bound / binary_search |
O(log n) |
必须有序 |
unique / remove |
O(n) |
unique 需先排序才能全局去重 |
find / count |
O(n) |
无 |
reverse / rotate / fill |
O(n) |
无 |
next_permutation |
均摊 O(n),全部枚举 O(n·n!) |
从升序开始 |
make_heap |
O(n) |
无 |
push_heap / pop_heap |
O(log n) |
已是堆 |
集合运算 / merge |
O(n + m) |
两个序列都有序 |
accumulate / partial_sum |
O(n) |
无 |
十四、高频错误清单#
- 无序区间上直接
lower_bound/binary_search→ 结果无意义,必须先排序。 - 降序数组用默认二分 → 比较器要传
greater<>,且语义反转。 - 自定义比较器写
<=→ 违反严格弱序,可能死循环或崩溃。 unique/remove后忘记erase→ 容器大小没变,“去重失败”。accumulate初始值写0求大数和 → int 累加溢出,用0LL。- 空区间解引用
min_element/max_element→ 未定义行为,先判空。 next_permutation没从升序开始 → 枚举不全,先sort。- 比较器中修改元素或捕获悬垂引用 → 未定义行为。
sort当稳定排序用 → 相等元素顺序不保证,需要稳定用stable_sort。random_shuffle→ C++17 已移除,用shuffle + mt19937。- 把
find用在无序大数组里反复查询 →O(n)每次,该用 set 或先排序二分。 - 算法不改变容器大小:
copy/transform目标区间必须已分配足够空间,或用back_inserter。
十五、一页速记#
#include <bits/stdc++.h>
using namespace std;
// 排序
sort(v.begin(), v.end()); // 升序
sort(v.begin(), v.end(), greater<int>()); // 降序
sort(v.begin(), v.end(), cmp); // 自定义(严格弱序)
stable_sort(v.begin(), v.end(), cmp); // 稳定排序
nth_element(v.begin(), v.begin() + k, v.end()); // 第 k 小,O(n)
// 二分(先有序)
int p = lower_bound(v.begin(), v.end(), x) - v.begin(); // 首个 >= x
int q = upper_bound(v.begin(), v.end(), x) - v.begin(); // 首个 > x
bool ok = binary_search(v.begin(), v.end(), x);
int cnt = q - p; // x 的个数
// 去重 / 删除
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
v.erase(remove(v.begin(), v.end(), x), v.end());
v.erase(remove_if(v.begin(), v.end(), pred), v.end());
// 最值 / 查找 / 统计
*max_element(v.begin(), v.end()); // 先判空
find(v.begin(), v.end(), x);
count(v.begin(), v.end(), x);
// 变形
reverse(v.begin(), v.end());
rotate(v.begin(), v.begin() + k, v.end()); // 左旋 k 位
shuffle(v.begin(), v.end(), rng);
// 填充 / 数值
fill(v.begin(), v.end(), -1);
iota(v.begin(), v.end(), 1); // <numeric>
accumulate(v.begin(), v.end(), 0LL); // 0LL 防溢出
partial_sum(v.begin(), v.end(), pre.begin()); // 前缀和
gcd(a, b); lcm(a, b); // C++17
// 全排列
sort(v.begin(), v.end());
do { /* ... */ } while (next_permutation(v.begin(), v.end()));
// 堆
make_heap(h.begin(), h.end());
push_heap(h.begin(), h.end());
pop_heap(h.begin(), h.end()); h.pop_back();cpp五句口诀:
- 所有算法操作
[first, last)左闭右开区间,数组传指针、容器传迭代器。 - 二分、集合运算必须先有序,比较器与排序规则一致。
unique/remove不改变容器大小,必须配erase。- 比较器用
</>严格弱序;accumulate用0LL防溢出。 - 第 k 小用
nth_element(O(n)),全排列用next_permutation(先升序)。