[算法学习]模板-STL与基础算法

在 OI 赛制（如蓝桥杯）中，绝对不要去手写队列、堆或者红黑树。C++ 的标准模板库 (STL) 就是官方提供的黑盒 API。熟练调用它们，能把 $O(N^2)$ 的暴力代码瞬间降维到 $O(N \log N)$。

---

📦 核心容器 API (Containers)

1. 动态数组 vector (图论基建)

物理内存连续的变长数组。它是图论中替代“二维数组存图”的终极武器（用于构建邻接表）。

#include <vector>

vector<int> v;
v.push_back(x);     // 在尾部极速插入元素 x (均摊 O(1))
v.pop_back();       // 弹出尾部元素
int len = v.size(); // 获取当前元素个数

// 遍历技巧：范围 for 循环 (C++11)
for(int x : v) {
    cout << x << " ";
}

2. 队列 queue (BFS 波纹引擎)

先进先出 (FIFO) 的数据结构。广度优先搜索 (BFS) 的唯一核心驱动器。

#include <queue>

queue<int> q;
q.push(x);          // 将 x 压入队尾 (入队)
int head = q.front(); // 获取队头元素 (注意：只获取，不弹出！)
q.pop();            // 弹出队头元素 (出队)
bool is_empty = q.empty(); // 判断队列是否为空，BFS 循环终止的核心条件

3. 优先队列 priority_queue (贪心与 Dijkstra 外挂)

底层是一棵“二叉堆”。无论你按什么顺序把数据扔进去，它总能以 $O(\log N)$ 的速度把最大（或最小）的元素浮到顶端。

#include <queue>

// 默认情况：大根堆（最大的元素在最上面）
priority_queue<int> pq_max; 
pq_max.push(x);
int max_val = pq_max.top(); // 获取最大值
pq_max.pop();               // 弹出最大值

// 核心改写：小根堆（最小的元素在最上面）
priority_queue<int, vector<int>, greater<int>> pq_min;

🚨 高危防雷：priority_queue 的反直觉排序 (以贪心区间调度为例)

在处理贪心问题时（比如经典的**“活动安排/区间调度问题”**：给 $N$ 个比赛的开始和结束时间，问最多能参加几个），我们经常需要自定义排序规则。

贪心核心思想：谁结束得越早，我就越先选谁！因为结束得越早，留给后面比赛的时间就越多。所以必须按结束时间从小到大排序。

【极其危险的暗雷】：priority_queue 的排序重载逻辑，和 sort 是完全相反的！

• 如果用 sort，升序你会写 A.endtime < B.endtime;（符合直觉）。
• 但 priority_queue 默认是大根堆（最大的在上面）。为了让结束时间最小的浮在堆顶，变成小根堆，你的比较逻辑必须反着写 >！

实战终极模板（自写结构体 + 仿函数重载）：

struct contest {
    int begintime;
    int endtime;
};

// 比较器：实现按结束时间从小到大出队
// 核心心法：return true 代表 A 的优先级比 B 低（A 会沉在 B 的下面）
struct CmpPQ {
    bool operator()(const contest& A, const contest& B) const {
        if(A.endtime != B.endtime) 
            return A.endtime > B.endtime; // 反直觉：写 '>' 才能把小的顶上去！
        else 
            return A.begintime > B.begintime; // 结束时间相同，开始时间小的在堆顶
    }
};

// 声明优先队列，传入我们写好的防雷比较器
priority_queue<contest, vector<contest>, CmpPQ> q;

// 贪心核心验收逻辑：
// int last_end = -1;
// 取出 q.top()，如果 cur.begintime >= last_end，就选中它，并更新 last_end = cur.endtime;

4. 集合 set 与 映射 map (红黑树 / 状态压缩)

底层由红黑树实现，维护一个严格有序且不重复的内存空间。

#include <set>
#include <map>

// set：自动去重 + 自动排序
set<int> s;
s.insert(5); 
s.insert(3);
s.insert(5); // 重复插入无效，集合内依然是 {3, 5}

// map：超级数组（键值对）。可以用字符串或极大数字作为下标！
map<string, int> mp;
mp["hello"] = 1;      // 记录字符串出现的次数
mp["world"]++;        // 极速频次统计

---

⚙️ 核心算法库 <algorithm>

必须引入头文件 #include <algorithm>。这是蓝桥杯前两道大题白嫖分数的绝对利器。

1. 极速排序 sort

采用内省式排序（快排+堆排+插入排序的结合体），时间复杂度极度稳定的 $O(N \log N)$。

int a[N];
// 对 a[1] 到 a[n] 进行从小到大排序 (左闭右开区间)
sort(a + 1, a + 1 + n); 

// 降序排序：传入 greater<int>()
sort(a + 1, a + 1 + n, greater<int>());

// 结构体自定义排序 (贪心算法必备)
struct Node { int w, v; };
bool cmp(Node a, Node b) {
    return a.w < b.w; // 按照 w 从小到大排
}
Node arr[N];
sort(arr + 1, arr + 1 + n, cmp);

2. 全排列生成器 next_permutation

暴力穷举的终极外挂！能够原地将数组变成字典序的下一个排列。有了它，一半的 DFS 全排列题目都可以免手写。

int a[4] = {0, 1, 2, 3}; // 必须先保证数组是升序的
do {
    // 此时 a[1] ~ a[3] 已经是一个新的全排列
    for(int i = 1; i <= 3; i++) cout << a[i] << " ";
    cout << "\n";
} while(next_permutation(a + 1, a + 1 + 3)); 
// 当所有排列生成完毕，函数返回 false，循环自动结束

---

🚀 实战进阶补丁 (Hotfix)

🛠️ 补丁 1：STL 的致命弱点 —— I/O 阻塞

C++ 的 cin 和 cout 为了兼容 C 语言的 stdio，底层加了极重的同步锁。在读取超过 $10^5$ 级别的数据时，极易导致 TLE（超时）。

物理防御：在 main 函数的第一行，永远无脑加上这句“解除封印”的代码：

ios::sync_with_stdio(false);
cin.tie(nullptr);
// 警告：加上这两句后，绝不能再混用 scanf/printf 和 cin/cout！

🛠️ 补丁 2：map 的内存爆炸陷阱

在使用 map<int, int> mp; 时，如果你只是想查询某个键是否存在，绝对不要写 if(mp[x] == 1)！

因为 mp[x] 会强行在红黑树里为你开辟一个默认值为 0 的新节点，瞬间吞噬内存。

正确判定姿势：

if (mp.count(x)) {
    // 键 x 确实存在
}