一维数组与桶计数¶
为什么需要数组？¶
要记录全班 50 位同学的成绩，定义 score1、score2……score50？代码没法看。数组一次开出一排带编号的「房间」：
基本用法¶
int a[6] = {17, 8, 25, 4, 9, 12}; // 定义并初始化
cout << a[0] << endl; // 访问 0 号房间：17
a[2] = 30; // 把 2 号房间的值改成 30
三个铁规矩：
- 下标从 0 开始：
a[6]的合法下标是 0~5，a[6]这个房间不存在 - 越界不报错：C++ 不检查下标，
a[100]可能读到垃圾值、甚至让程序离奇崩溃——数组越界是竞赛里最隐蔽的错误 - 大小最好是常量：
int n; cin >> n; int a[n];这种「变长数组」不标准，竞赛中请int a[100005];开够题目上限
和循环是天作之友¶
下标是规律的，用 for 遍历一气呵成：
#include <iostream>
using namespace std;
int main() {
int a[10];
int n = 10;
for (int i = 0; i < n; i++) { // 读入
cin >> a[i];
}
int sum = 0;
for (int i = 0; i < n; i++) { // 求和
sum += a[i];
}
cout << sum << endl;
return 0;
}
桶计数：数组的第一个大招¶
问题：读入 \(n\) 个数（每个数都在 1~100 之间），问每个数出现了多少次？
开 100 个「桶」，数字是几就丢进几号桶，最后数每个桶里有多少个：
#include <iostream>
using namespace std;
int cnt[105]; // 桶数组，cnt[v] 表示数字 v 出现的次数
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
cnt[x]++; // 数字 x 出现一次，x 号桶 +1
}
for (int v = 1; v <= 100; v++) {
if (cnt[v] > 0) {
cout << v << " 出现了 " << cnt[v] << " 次" << endl;
}
}
return 0;
}
注意妙处：不需要先读完全部再统计——来一个数记一个，cnt[x]++ 一行搞定，连数组存原始数据都省了。
桶思想的应用
「统计字母出现次数」→ 开 cnt[26]，用 c - 'a' 当下标；
「判断哪些数出现过」→ 桶里存 0/1 当标记。这个套路第 5 章枚举、
后面很多算法里都会反复出现。
初始化的小知识¶
- 定义在
main外面的全局数组会自动清零：int cnt[105];全是 0，可直接cnt[x]++ - 定义在
main里面的局部数组初值是随机垃圾，用前要先清：memset或写循环赋 0，也可以int a[10] = {};全零初始化
竞赛代码习惯把大数组开成全局数组，就图「自动清零 + 栈空间无忧」。
例题 1：摘苹果¶
题目描述 树上挂着 \(n\) 个苹果，第 \(i\) 个苹果距离地面 \(h_i\) 厘米。陶陶站立时手能够到 \(150\) 厘米，踩上 \(30\) 厘米高的凳子后能多够到 \(30\) 厘米。问陶陶最多能摘到几个苹果？
输入格式 第一行一个整数 \(n\)；第二行 \(n\) 个整数，表示每个苹果的高度。
输出格式 一个整数，能摘到的苹果个数。
数据范围 \(1 \le n \le 1000\)，\(100 \le h_i \le 200\)。
样例输入 / 样例输出
思路分析 能够到的最大高度是 \(150 + 30 = 180\) 厘米，所以就是「数一数 \(h_i \le 180\) 的个数」——遍历数组加计数，一步到位。
参考代码
#include <iostream>
using namespace std;
int h[1005];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> h[i];
}
int cnt = 0;
for (int i = 0; i < n; i++) {
if (h[i] <= 150 + 30) cnt++;
}
cout << cnt << endl;
return 0;
}
同款题：洛谷 P1046 陶陶摘苹果（它还藏了个小陷阱：身高和凳子都从输入读，别写死 180）。
例题 2：校门外的树¶
题目描述 校门外有一条长 \(L\) 米的马路，从 \(0\) 到 \(L\) 每个整数位置都种了一棵树。现在要修建地铁，每修一段区间 \([l, r]\)，区间里的树全部被移走。求修完所有区间后马路上还剩多少棵树。
输入格式 第一行两个整数 \(L\)、\(M\)；接下来 \(M\) 行，每行两个整数 \(l\)、\(r\)。
输出格式 一个整数，剩下的树的棵数。
数据范围 \(1 \le L \le 10000\)，\(1 \le M \le 100\)，\(0 \le l \le r \le L\)。
样例输入 / 样例输出
思路分析 开一个 bool 数组当「树的存在标记」：先全部标为「有树」，每读一个区间就把对应位置标为「无树」。注意重叠区域（比如样例中 150~300 和 100~200 在 150~200 重叠）——被标记过两次也没关系，因为我们要的只是「最终还在不在」。这就是第 5 章模拟思想的雏形。
参考代码
#include <iostream>
using namespace std;
bool tree[10005]; // tree[i] = true 表示位置 i 有树
int main() {
int L, M;
cin >> L >> M;
for (int i = 0; i <= L; i++) tree[i] = true; // 先全部种上树
for (int k = 0; k < M; k++) {
int l, r;
cin >> l >> r;
for (int i = l; i <= r; i++) tree[i] = false; // 拔掉区间里的树
}
int cnt = 0;
for (int i = 0; i <= L; i++) {
if (tree[i]) cnt++;
}
cout << cnt << endl;
return 0;
}
这就是洛谷 P1047 校门外的树，信奥圈人尽皆知的入门题。
动手试一试¶
- 读入 10 个整数，倒序输出
- 读入 n 个 0~9 的数字，输出出现次数最多的数字（如有多个输出最小的）
- 经典开灯问题：n 盏灯初始全亮，经过 k 轮，第 i 轮拨动所有编号是 i 的倍数的灯（亮变灭、灭变亮），问最后哪些灯灭着（提示：模拟 + 数组标记）
- 挑战：统计一句话里 26 个字母各出现多少次（不区分大小写，用
char数组 +getline读整行）
下一课，让数据排好队：排序：冒泡与选择。