麦地

Back

#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 后 second
cpp

比较器必须满足严格弱序:

  • 用 < 或 >,不能用 <= / >=(违反”自己不大于自己”,导致未定义行为甚至崩溃);
  • 不能比较过程中修改元素;
  • 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];
cpp

6. 排序相关检查#

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());
cpp

unique 只把相邻重复元素移到尾部并返回新逻辑尾,不改变容器大小。全局去重必须先 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());                                          // 删所有偶数
cpp

remove 同样不改变容器大小,只是把保留元素前移。复杂度 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); // 两迭代器指向的元素
cpp

rotate 常用于循环位移、把某段移到开头。


七、填充与生成#

iota + sort 的”下标排序”是保留原位置信息的经典技巧。


八、数值算法(<numeric>)#


九、全排列(枚举神器)#

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:从降序开始反向枚举
cpp
  • next_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):

竞赛中手写双指针也很常见,库函数版更不易写错。


十二、拷贝与遍历#


十三、复杂度速查表#

算法 复杂度 前提
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) 无

十四、高频错误清单#

  1. 无序区间上直接 lower_bound / binary_search → 结果无意义,必须先排序。
  2. 降序数组用默认二分 → 比较器要传 greater<>,且语义反转。
  3. 自定义比较器写 <= → 违反严格弱序,可能死循环或崩溃。
  4. unique / remove 后忘记 erase → 容器大小没变,“去重失败”。
  5. accumulate 初始值写 0 求大数和 → int 累加溢出,用 0LL。
  6. 空区间解引用 min_element / max_element → 未定义行为,先判空。
  7. next_permutation 没从升序开始 → 枚举不全,先 sort。
  8. 比较器中修改元素或捕获悬垂引用 → 未定义行为。
  9. sort 当稳定排序用 → 相等元素顺序不保证,需要稳定用 stable_sort。
  10. random_shuffle → C++17 已移除,用 shuffle + mt19937。
  11. 把 find 用在无序大数组里反复查询 → O(n) 每次,该用 set 或先排序二分。
  12. 算法不改变容器大小:copy/transform 目标区间必须已分配足够空间,或用 back_inserter。

十五、一页速记#

五句口诀:

  1. 所有算法操作 [first, last) 左闭右开区间,数组传指针、容器传迭代器。
  2. 二分、集合运算必须先有序,比较器与排序规则一致。
  3. unique/remove 不改变容器大小,必须配 erase。
  4. 比较器用 </> 严格弱序;accumulate 用 0LL 防溢出。
  5. 第 k 小用 nth_element(O(n)),全排列用 next_permutation(先升序)。
Comment seems to stuck. Try to refresh?✨