章节概述
数组是一组相同类型数据的连续存储结构，是最基础的数据组织方式。
支持 O(1) 随机访问，是几乎所有高级数据结构的基础。
核心原理
1. 数组的内存模型
int a[5]; // 连续 5 × sizeof(int) 字节
地址: &a[0], &a[1], &a[2], &a[3], &a[4]
- 下标从 0 开始: a[0] 到 a[n-1]
- 全局数组自动初始化为 0；局部数组不会
- 数组名退化为指向首元素的指针
2. 初始化方式
int a[100] = {0}; // 全零
int a[100] = {1, 2, 3}; // 前三个指定，其余为0
int a[] = {1, 2, 3}; // 自动推断大小为3
fill(a, a + n, true); // fill 填充
memset(a, 0, sizeof(a)); // 按字节清零3. 桶/标记数组
用数组下标作为”键”实现 O(1) 查询:
bool exist[20001] = {0}; // 标记数字是否出现
int cnt[2005] = {0}; // 计数数组关键数据结构
- E_容器_Container — vector 是动态数组
- I_排序_八大排序_Sorting — 排序算法作用于数组
P1046 [NOIP2005 普及组] 陶陶摘苹果
题目: 陶陶手高 + 板凳 30cm，求能摘到的苹果数量。
#include <iostream>
using namespace std;
int main() {
int a[10], h, cnt = 0;
for (int i = 0; i < 10; i++) cin >> a[i];
cin >> h;
h += 30;
for (int i = 0; i < 10; i++)
if (a[i] <= h) cnt++;
cout << cnt << endl;
return 0;
}P1047 [NOIP2005 普及组] 校门外的树
题目: 长度为 L 的马路上挖掉 M 个区间内的树，求剩余数量。用布尔数组标记。
#include <iostream>
using namespace std;
int main() {
int L, M;
cin >> L >> M;
bool tree[10001];
fill(tree, tree + L + 1, true);
for (int i = 0; i < M; i++) {
int u, v;
cin >> u >> v;
for (int j = u; j <= v; j++)
tree[j] = false;
}
int cnt = 0;
for (int i = 0; i <= L; i++)
if (tree[i]) cnt++;
cout << cnt << endl;
return 0;
}P1428 小鱼比可爱
题目: N 条鱼，求每条鱼左边有多少条不及自己可爱的鱼。
#include <iostream>
using namespace std;
int main() {
int n, a[100];
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++) {
int cnt = 0;
for (int j = 0; j < i; j++)
if (a[j] < a[i]) cnt++;
cout << cnt << " ";
}
return 0;
}P2141 [NOIP2014 普及组] 珠心算测验
题目: n 个不同正整数，求有多少个数恰好等于另外两个不同数之和。用桶标记避免重复统计。
#include <iostream>
using namespace std;
int main() {
int n, a[101], exist[20001] = {0}, ans = 0;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
exist[a[i]] = 1;
}
for (int i = 0; i < n - 1; i++)
for (int j = i + 1; j < n; j++) {
int sum = a[i] + a[j];
if (sum <= 20000 && exist[sum] > 0) {
ans++;
exist[sum] = -1;
}
}
cout << ans << endl;
return 0;
}推荐练习题（洛谷）
相关技巧
多平台练习
| 洛谷 | 本题单 | 竞赛基础 |
| POJ (北大) | PKU JudgeOnline | 经典题目，适合巩固 |
| HDU (杭电) | HDU OJ | 暑期多校训练 |
| Codeforces | Codeforces | 国际竞赛，适合提升 |