专题10 · 数据结构2

🔧 vector　0–15′

动态数组：内存连续、可随机访问。
解决：长度事先未知、要按下标查询。

🏆 priority_queue　15–25′

二叉堆：每次拿最大 / 最小。
解决：反复「取两个最值再合并」。

🚪 deque　25–32′

双端队列：两端增删 O(1)，还能随机访问。
解决：两头都要动、还要查中间。

罪一：长度写死

开 int a[100]，第 101 个数据来了怎么办？开大了浪费、开小了 RE。
vector：push_back 自己长大。

罪二：删中间很痛

删掉 a[3] 要把后面全部前移，代码一多就写错边界。
vector：erase 帮你搬。

罪三：两端不能动

数组头部插入 = 全体后移；queue 又只能一头进一头出。
deque：两头都是 O(1)。

vector 的一句话画像

一块连续内存 + 自动扩容。v[i] 是 O(1)（因为连续，直接算地址）。

为什么"连续"这么重要

连续才能指针 +i 直接定位、才能二分、才能被 CPU 缓存预读。 list（链表）不能随机访问，就是因为它不连续。

扩容到底做了什么

容量不够 → 申请一块新空间（通常翻倍） → 把旧元素全部拷贝过去 → 释放旧空间。 所以扩容那一次是 O(n)，但因为翻倍，均摊下来 push_back 仍是 O(1)。

考试怎么用这条性质

如果事先知道要放 1e5 个元素，先 v.reserve(100000);， 一次都不用搬家，常数直接小一大截。

尾部操作是主场

push_back / pop_back：O(1)，不牵动任何其它元素。

v.front() / v.back() / v[i] / v.size() / v.empty()

中间/头部操作是客场

insert / erase 在头部或中间：O(n)，后面的元素要整体搬家。

v.begin() 首　v.end() 尾后一位
v.rbegin() 反向首

① 二维 vector

int n, m; cin >> n >> m;
vector<vector<int>> a(n,
       vector<int>(m, 0));
// a[i][j] 直接用，行数列数运行时才定

比 int a[505][505] 好在：不浪费、不越界、能当参数传。

② 结构体 vector

struct Node{ int x, y, w; };
vector<Node> v;
v.push_back({1, 2, 3});
sort(v.begin(), v.end(),
  [](Node a, Node b){
    return a.w < b.w;   // 按 w 升序
  });

排序 + 结构体是复赛最高频组合。

③ 邻接表存图

vector<int> g[100005];
// 加一条 u → v 的边
g[u].push_back(v);
// 遍历 u 的所有邻居
for(int v : g[u]) { ... }

每个点一条"边链表"，点数不定也能存。

建模关键

帖子编号就是桶的下标；"第 y 个回复"是 1-based，代码里要 [y-1]。

为什么不用二维数组

10 万个帖子 × 回复数不定 —— 开二维数组要么爆内存、要么不够用。每个帖子一个 vector，按需生长。

数组 ↔ 树 的位置关系

结点 i 的父：(i-1)/2；左孩子：2i+1；右孩子：2i+2（0-based）。
完全二叉树不会在中间留洞，所以能用一个紧凑数组表示。

复杂度

插入 / 删除：O(log n)（只沿一条父子链上下移动，树高 log n）。
取最值 top()：O(1)。
建堆 O(n)。

① greater（推荐）

priority_queue<
  long long,
  vector<long long>,
  greater<long long> > pq;

顶部是最小值。记得 #include <functional>。

② 取负数（常用技巧）

priority_queue<long long> pq;
pq.push(-w);            // 存负数
long long mn = -pq.top(); // 取回

大顶堆堆顶是"最大的负数"＝最小的原值。

③ 结构体自定义比较

struct Node{ int w, id; };
struct Cmp{
  bool operator()(
      const Node& a, const Node& b) const{
    return a.w > b.w;  // w 小的优先
  }
};
priority_queue<Node, vector<Node>, Cmp> q;

注意方向：返回 true 表示 a 的优先级更低（反直觉，写反了会调半天）。

deque 为什么两头都快

它不是一整块连续内存，而是若干块缓冲区 + 一个中控数组（map）。 前面要加元素就在前面新开一块，不用动已有元素。

代价是什么

因为不连续，它的常数比 vector 略大；at(i) 仍是 O(1)（中控数组定位块 + 块内偏移）， 但缓存友好性不如 vector。

① 长度不定 + 要按下标查

→ vector。
信号词："第 k 个"、"动态追加"。

② 反复"取两个最值合并"

→ priority_queue。
信号词："最小的两个"、"每次取最大"。

③ 一头进新、一头掉旧 + 要查

→ deque。
信号词："滑动窗口"、"有效期"、"最近 k 个"。

为什么必须是 deque

龙头移动 Q 次（1e5），每次都要头部加、尾部删：vector 头插是 O(n) 直接 TLE； queue 又不能按下标查第 k 节。只有 deque 两头 O(1) 且能 at(k)。

代码骨架

deque<pair<int,int>> body;
// 走一步
body.push_front({nx, ny});
body.pop_back();
// 查第 k 节（1-based）
auto p = body[k-1];

① 特判档：先别想算法，看数据范围表

题目给的数据范围表就是出题人给你的送分清单。看到「n = 1」「只有一组数据」这类一行， 就先写个 if 直接输出答案。2 分钟换 5~10 分，全场最划算。

② 暴力档：按题意最直白地写一遍

多重循环、DFS 全枚举、朴素 O(n³)……不要优化，只要保证最小那档全对。 它既是保底分，又是后面对拍的标尺——没有它你无法证明正解是对的。

③ 特殊性质档：题目里那句「若……」

常见的送分性质：数据已经有序、所有值完全相同、规模小到可以 O(n²)、 只出现一种类型。题目写出来就是让你拿的，专门写一份即可。

④ 正解档：思路定了，就赢了八成

考场上的时间几乎都花在想思路上，不是写代码。写完先跑样例， 再用第 ② 档的暴力版造小数据对拍——这是唯一能证明你思路对的办法。

论坛帖子（vector） · FORUM

第1档 · 2 分钟
n == 1 → 直接输出那一条

第2档 · 8 分钟
定长数组开大 + 手动移动元素，n ≤ 10⁴ 稳过

第3档 · 10 分钟
只有新增、没有删除/插入 → 就是顺序输出

第4档 · 15 分钟
vector + 迭代器按条件查找与删除

哈夫曼树的带权路径长度 · HUFFMAN

第1档 · 2 分钟
n == 1 → 0

第2档 · 8 分钟
每次线性扫描找最小两个合并，O(n²)，n ≤ 10³ 稳过

第3档 · 10 分钟
所有权重相同 → 就是满二叉树，WPL 可直接算

第4档 · 15 分钟
小顶堆 priority_queue，每次取两个最小的合并，累加

公交换乘 · BUS

第1档 · 2 分钟
没有任何地铁（优惠券）记录 → 答案 = 所有票价之和

第2档 · 8 分钟
每张公交票往前扫所有未用券，n ≤ 10³ 时 O(n²) 稳过

第3档 · 10 分钟
所有票价相同 → 直接配对计数

第4档 · 15 分钟
deque 按时间维护 45 分钟内未使用的券，每张票从队首找可用券