前三节都是“读一个、算一个、扔掉”。这一节解决回头访问：先把 n 个数存起来，再按编号取。10 个数能起 10 个变量名，10⁵ 个不行。数组 = 一块连续内存 + 从 0 开始的编号，编号叫下标，写 a[i]。
陶陶家的苹果树结了 10 个苹果。她有一个 30 厘米高的板凳，手够不到就踩上去再试。已知 10 个苹果到地面的高度和陶陶把手伸直时能达到的最大高度，求她最多能摘到几个苹果（碰到就掉下来）。
输入两行：第一行 10 个 100~200 的整数（厘米），表示各苹果的高度；第二行 1 个 100~120 的整数（厘米），表示把手伸直时能达到的最大高度。
输出一行一个整数，表示能摘到的苹果数。
输入顺序是关键：10 个高度在前，手的高度在后。要判断够不够得到，必须先拿到手的高度，而它在最后。所以这 10 个数非存不可——数组存在的第一个理由。
本节只有三样新东西。
| 组成 | 含义 / 格式要求 |
|---|---|
int a[100005]; | 下标 0~100004。长度必须是编译期常量，不能是读进来的 n。 |
a[0] … a[长度-1] | 长度 10 的数组，最后一个元素是 a[9]，没有 a[10]。 |
a[i] | i 可以是变量或表达式（如 a[i*2+1]），只要结果在范围内。 |
全局 / 局部 | main 外：自动全 0、不占栈。main 里：随机值，大数组还会爆栈。 |
内存布局 | a[i] 的地址 = 起始地址 + i×4，连续存放，随机访问 O(1)。 |
#include <bits/stdc++.h>
using namespace std;
const int N = 100005; // 长度写成常量，改一处就够
int a[N]; // 全局：默认全 0，占 400KB，不放栈上
int main() {
int n; cin >> n;
for (int i = 0; i < n; ++i) cin >> a[i]; // 只填前 n 个格子
for (int i = n - 1; i >= 0; --i) cout << a[i] << " ";
cout << "\n";
return 0;
}长度只能开大不能开小：n ≤ 10⁵ 就开 100005，多留 5 格防差一。
局部 int a[1000005]; 占 4MB 栈，栈上限常只有 1~8MB，直接 RE。挪到 main 外。
下标从 0 开始：a[i] 的地址是 base + i×4，索引 0 正好落在起始地址。
| 组成 | 含义 / 格式要求 |
|---|---|
sizeof(a) | 整个数组的字节数。int a[10] 得 40。 |
sizeof(a[0]) | 单个元素：int 4、long long 8、char 1、double 8。 |
sizeof(a)/sizeof(a[0]) | 数组长度，换元素类型不用改公式。 |
编译期求值 | 是运算符不是函数，没有运行时开销。 |
数组退化后失效 | 传进函数后 a 变成指针，sizeof(a) = 8，公式作废。 |
#include <bits/stdc++.h>
using namespace std;
int main() {
int a[10];
cout << sizeof(a) << "\n"; // 40 = 10 × 4
cout << sizeof(a[0]) << "\n"; // 4
cout << sizeof(a) / sizeof(a[0]) << "\n"; // 10，就是长度
return 0;
}竞赛里更常见的是直接用读入的 n，别依赖 sizeof——数组传进函数后它会骗你。
sizeof 是无符号数，与 int 比较会有警告，写成 (int)(sizeof(a)/sizeof(a[0])) 最干净。
| 组成 | 含义 / 格式要求 |
|---|---|
for (int x : a) | 从头到尾取每个元素，复制给 x。不写下标，不会写错边界。 |
int &x | 引用即别名，改 x 就是改数组。要修改元素时用它。 |
走多少格 | 整个数组长度，一格不少。不能只走前 n 个，不能倒序或跳跃。 |
什么时候不能用 | 需要下标（问“第几个”）、倒序、或数组开大了只读 n 个数时。 |
版本 | C++11 起，C++17 当然支持。 |
#include <bits/stdc++.h>
using namespace std;
int main() {
int a[5] = {3, 1, 4, 1, 5}, s = 0;
for (int x : a) s += x; // 副本：s = 14，a 没变
for (int &x : a) x *= 2; // 引用：a 变成 6 2 8 2 10
for (int x : a) cout << x << " ";
cout << "\n" << s << "\n";
return 0;
}最大的坑：int a[100005]; 只读了 5 个数，for (int x : a) 会把后面 100000 个 0 也算进去，答案大出一截。
范围 for 拿不到下标。答案要输出“位置”的题，老实写普通 for。
判断规则一句话：苹果高度 ≤ 可及高度就摘得到，而可及高度 = 手伸直高度 + 30。
h[0..9]，再读入手的高度 reach；h[i] <= can 就 ++ans。第 3 步是通用骨架：答案变量归零 → 遍历 → 满足条件就更新。计数、求和、求最值、找位置，都只是换一行循环体。
#include <bits/stdc++.h>
using namespace std;
int main() {
int h[10];
for (int i = 0; i < 10; ++i) cin >> h[i]; // ① 先全部读入：手的高度还没出现
int reach;
cin >> reach; // ② 再读手能到达的高度
int can = reach + 30; // ③ 踩上 30cm 板凳后，把 30 只加一次
int ans = 0; // ④ 计数器必须从 0 开始
for (int i = 0; i < 10; ++i)
if (h[i] <= can) ++ans; // 碰到就掉，计一个
cout << ans << "\n";
return 0;
}| 代码片段 | 含义与理由 |
|---|---|
int h[10]; | 10 个格子，合法下标 0~9。只有 40 字节，开在 main 里也无所谓。 |
for (int i = 0; i < 10; ++i) cin >> h[i]; | 循环 10 次，第 i 次读的数放进 h[i]。cin 自动跳过空格换行，数据分几行写都行。 |
cin >> reach; | 第 11 个数正好是第二行那个高度。顺序不能反。 |
int can = reach + 30; | 题目给的高度不含板凳。先加进 can，循环里就只剩一次判断。 |
int ans = 0; | 必须显式初始化。局部变量不初始化是随机值，可能输出 1245123。 |
for (int i = 0; i < 10; ++i) | 0 到 9 正好 10 个。写成 i <= 10 就会访问 h[10]，越界。 |
if (h[i] <= can) ++ans; | 等于也算，题目说碰到就掉，别写成小于。 |
cout << ans << "\n"; | 只输出数字，不加提示文字。 |
把骨架换几行循环体，就得到四种统计。只有求最值有一个必须想清楚的细节：初值怎么选。
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int a[N];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; ++i) cin >> a[i]; // 先全部读入
int mx = a[0], mn = a[0]; // 初值取第一个元素，不是 0
long long sum = 0; // n 大、值大时必须 long long
for (int i = 0; i < n; ++i) {
if (a[i] > mx) mx = a[i]; // 严格大于才换，相等时保留先出现的
if (a[i] < mn) mn = a[i];
sum += a[i];
}
cout << mx << " " << mn << " " << sum << "\n";
return 0;
}| 代码片段 | 含义与理由 |
|---|---|
int mx = a[0]; | a[0] 是真实数据，不可能比最大值大，结果无条件正确。 |
int mx = 0; | 只在全 ≥ 0 时对。输入 -5 -9 时 mx 停在 0，输出 0 —— WA。 |
int mx = INT_MIN; | 同样永远正确，需 <climits>（bits 已含），但看不出含义。 |
if (a[i] > mx) | 用 > 不用 >=：相等时不覆盖，保留“第一次出现”的信息。 |
sum += a[i]; | 同一循环顺手算完，不必多扫一遍数组。 |
| 目的 | 初始化 | 循环体 | 写错会怎样 |
|---|---|---|---|
| 求和 | 0（用 long long） | sum += a[i]; | 用 int 溢出 → 输出负数 |
| 计数 | 0 | if (条件) ++cnt; | 没初始化 → 随机数 |
| 最大值 | a[0] 或 INT_MIN | if (a[i] > mx) mx = a[i]; | 初值 0 → 全负数时 WA |
| 最小值 | a[0] 或 INT_MAX | if (a[i] < mn) mn = a[i]; | 初值 0 → 全正数时 WA |
| 第一次位置 | -1 | if (a[i]==x) { pos=i; break; } | 初值 0 → 没找到时错答 1 |
必须存：需要回头访问。如本题（手的高度在后面）、两两比较、统计频率、按原顺序输出。
可以不存：求和、计数、求最值。只用“当前元素”和“已有答案”，内存 O(1)。n = 10⁶ 个 int 要 4MB，老题内存常只给 8~16MB。
口诀：答案里出现“前 i 个”就不用数组；出现“第几个 / 后面还要用”就必须存。
越界：int a[10] 却写 i<=10。症状：本地正常，洛谷 RE 或偶发 WA。
数组开小：n ≤ 10⁵ 却开 a[1000]。症状：RE 与随机 WA 交替，重交结果还不同——数组题最典型的指纹。
最值初值取 0：数据 -5 -9 时输出 0。症状：样例过、一交就 WA，只错在负数数据点。
局部大数组爆栈：int a[1000005]; 写在 main 里占 4MB 栈。症状：一启动就 RE，一行输出都没有。
求和用 int：n = 10⁵、每数 10⁹，总和 10¹⁴ 超上限。症状：输出负数。
范围 for 扫了没读过的尾巴：只读 5 个数却 for (int x : a)。症状：答案大出一截。
关掉页面，把 P1046 的代码从头敲一遍并提交。
改一：把 10 换成先读 n（n ≤ 100），再读 n 个高度，最后读手的高度，所有循环条件跟着 n 走。
改二：输出“能摘到的苹果里最高的高度”，一个都摘不到输出 -1。想清楚 mx 初值该取什么，照抄 a[0] 会错在哪。
求最大值那个 if 凭什么正确？可以用数学归纳法证明。方法是给循环写一条循环不变式：关于“第 k 轮开始时什么成立”的断言。
if (a[i] > mx) mx = a[i];（i = k-1）。若 a[k-1] 更大则 mx 换成它，否则不变，两种情形下 mx = max(a[0..k-1]) 仍成立。三步就是全部。以后学前缀和、单调栈、DP，证明正确性用的都是同一套话，只是不变式内容不同。养成习惯：任何“维护一个答案变量”的循环，先用一句话说清不变式。
推论 1（数个数）：区间 [l, r] 内整数个数 = r − l + 1。长度 n 的数组合法下标是 0..n−1，个数 = (n−1) − 0 + 1 = n，所以循环条件永远是 i < n。所有差一错误都能用这个公式当场算穿。
推论 2（别乱排序）：求最值一遍遍历 O(n)，排序后取端点 O(n log n)。
| n | 一遍遍历 ≈ n 次 | 排序 ≈ n·log₂n 次 | 倍数 |
|---|---|---|---|
| 10³ | 1 000 | 约 10 000 | 10× |
| 10⁵ | 100 000 | 约 1.7×10⁶ | 17× |
| 10⁶ | 1 000 000 | 约 2×10⁷ | 20× |
结论：能在读入时顺手维护的信息（和、最值、计数），不要为了“先存后算看着清楚”多存一个数组、多排一次序。
const int N = 100005; int a[N];，并说出大数组为什么写在 main 外。sizeof(a)/sizeof(a[0]) 在什么情况下失效，以及竞赛里为什么更爱用 n。i < j 枚举时，同一对只被数一次。有 N 名同学参加期末考试，每人有语文、数学、英语三科成绩，均为不超过 150 的自然数。
如果两名同学三科成绩两两之间的差距都不超过 5 分，且总分差距不超过 10 分，就称这两个同学是一对“旗鼓相当的对手”。求一共有多少对。
输入格式：第一行一个整数 N（2 ≤ N ≤ 1000）；接下来 N 行，每行三个整数，表示一名同学的三科成绩。
输出格式：一行一个整数，表示“旗鼓相当的对手”的对数。
先想清楚“一对”怎么数才不重不漏：i、j 都从 0 跑到 n−1 的话，每对会被数两次。
三科差和总分差是四条独立判断，缺一条答案就偏大。
N = 1000 时一共有多少对？先估这个数量级，再决定二重循环够不够。
用平行数组存三科：ch[i]、ma[i]、en[i] 属于同一个人。
读入时把总分算好存进 tot[i]，避免内层循环里重复加三次。
二重循环：外层 i 从 0 到 n−1，内层 j 从 i+1 到 n−1，每对 (i, j) 恰好检查一次。
四个条件全满足才计数：三个单科差 ≤ 5，总分差 ≤ 10，用 abs 取绝对值。
复杂度 O(n²)，n = 1000 时约 5×10⁵ 次比较，1 秒内轻松跑完。
#include <bits/stdc++.h>
using namespace std;
const int N = 1005; // n ≤ 1000，多留 5 格防差一
int ch[N], ma[N], en[N], tot[N]; // 平行数组 + 总分，全局默认全 0
int main() {
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> ch[i] >> ma[i] >> en[i];
tot[i] = ch[i] + ma[i] + en[i]; // 总分只依赖本人，读入时算一次就够
}
int ans = 0;
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j) { // j 从 i+1 起：每对只数一次
if (abs(ch[i] - ch[j]) <= 5 &&
abs(ma[i] - ma[j]) <= 5 &&
abs(en[i] - en[j]) <= 5 &&
abs(tot[i] - tot[j]) <= 10) ++ans;
}
cout << ans << "\n";
return 0;
}| 片段 | 作用 |
|---|---|
int ch[N], ma[N], en[N], tot[N]; | 四个平行数组，同一下标 i 指向同一个人。写 main 外：默认全 0，不占栈。 |
tot[i] = ch[i] + ma[i] + en[i]; | 总分读入时算一次。放进内层循环会重复算 n 遍。 |
for (int j = i + 1; j < n; ++j) | 关键一行。保证 (i,j) 与 (j,i) 只被算一次；写成 j = 0 答案必翻倍。 |
abs(ch[i] - ch[j]) <= 5 | abs 取绝对值，两个方向的差都变正。成绩 ≤ 150，int 足够。 |
&& 连四个条件 | 短路求值：前一个不成立就不再判断后面的，既对又快。 |
for (j = 0; ...)，答案正好是正确值的 2 倍。样例若是 0 就看不出，交上去必 WA。i <= n，下标取到 n，越界写坏 tot 后面的内存，随机 WA。