本讲定位：三级编程题的”武器库”。上一讲解决的是”数组怎么用”，本讲解决的是”数组能干什么”。官方大纲对数组只有一句话，但三级编程题的第 1 题几乎必是本讲的某一个套路，第 2 题往往是两三个套路的组合。本讲的六个套路每一个都短（三到六行），价值不在难度，而在必须写到不用想——考场上省下来的时间全部要留给第 2 题。其中**「桶」是三级唯一一个真正算得上”算法思想”的东西**，也是本讲的重点。
对应官方大纲：三级知识块 5「数据结构」——C++ 一维数组（不包括变长数组）。
前置知识：三级第 04 讲（一维数组基础——本讲全部建立在它之上）、一级第 08 讲（循环）、二级第 07 讲（多重循环）、二级第 08 讲（
max/min）。代码说明：本讲所有代码均已用 g++ 11.5（
-std=c++11）编译运行验证，输出结果即为文中标注结果。
第一道（读程序写结果）：
int a[5] = {3, 7, 2, 7, 5}; int mx = 0, pos = 0; for (int i = 0; i < 5; i++) { if (a[i] > mx) { mx = a[i]; pos = i; } } cout << mx << " " << pos;输出是（ ）
第二道（编程题）：
输入 $n$ 个 1 到 100 之间的整数，统计每个数出现了几次，按从小到大输出所有出现次数最多的数。
答案：第一道输出
7 1。
- 打擂台求最大值，
7第一次出现在下标 1，后面那个 7 不满足”严格大于”，所以位置不会被更新。mx初值设成 0 在这道题里侥幸没错（因为数据全是正数）。如果数组里全是负数，答案就会错成 0——这是本讲第一个坑，第 4 节详谈。第二道题就是”桶”的标准应用，用普通办法要写二重循环（$O(n^2)$），用桶只要两个单层循环。这道题的两种写法差别，是本讲最值得学的东西。
| # | 套路 | 核心代码 | 复杂度 |
|---|---|---|---|
| 1 | 求和 / 平均 | sum += a[i] |
$O(n)$ |
| 2 | 最值 + 位置（打擂台） | if (a[i] > mx) { mx = a[i]; pos = i; } |
$O(n)$ |
| 3 | 条件统计 | if (条件) cnt++ |
$O(n)$ |
| 4 | 顺序查找 | 找到就 break，记下标 |
$O(n)$ |
| 5 | 桶（计数数组） | cnt[a[i]]++ |
$O(n + V)$ |
| 6 | 反转 / 插入 / 删除 | 双指针交换 / 整体搬移 | $O(n)$ |
六个套路共用一个骨架——都是第 04 讲那个遍历模板，只是循环体里那一行不同：
for (int i = 1; i <= n; i++) {
// ← 六个套路的区别全在这一行
}
💡 本讲的学习方法：不要把六个套路当六件事背，把它们当成”同一个循环里换一行”。学生一旦建立这个认识，数组题的恐惧就消失了。
long long sum = 0; // ① 累加器初值为 0
for (int i = 1; i <= n; i++) sum += a[i]; // ② 逐个加
double avg = (double)sum / n; // ③ 平均要转 double
三个必须讲的点：