数组

数组

1. 数组的介绍

2. 数组的规则

2.1 下标规则

• 访问数组：$a[i]$
• $i$ 必须是“整数表达式”（例如 int / long long），不能是小数
• 如果数组长度是 $n$，并且下标从 $0$ 开始：
- 合法范围：$0 \sim n-1$
- 访问 $a[n]$ 是越界（$RE$）

最常用循环写法：

~~~cpp
for (int i = 0; i < n; i++) {
// 使用 a[i]
}
~~~



2.2 数组长度规则



数组的写法是：

~~~cpp
int a[N];
~~~

要求：

• $N$ 必须是“常量”（数字 ，或者 const 常量）
• $N$ 要开得足够大，保证不会越界，通常情况下会比题目中给出的数据多一点

例如：

~~~cpp
const int N = 200000 + 5;
int a[N];
int b[200005];
const int M = 2e5 + 5;//等价于200000 + 5
int c[M];
int d[2e5 + 5];//报错 , 2e5 + 5 不是一个常数
~~~

---



3. 数组的定义





3.1 全局数组



把数组写在 main 外面：

~~~cpp
#include <bits/stdc++.h>
using namespace std;

const int N = 200000 + 5;
int a[N]; // 全局数组

int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
return 0;
}
~~~

全局数组特点：

1) 默认会自动初始化为 $0$（没赋值也全是 $0$）
2) 可以开得比较大（适合 $n$ 很大）
3) 作用范围包含整个程序（哪里都能用）

---



3.2 局部数组



把数组写在函数里面（例如 main 里）：

~~~cpp
int main() {
int a[1000]; // 局部数组
int n;
cin >> n;
int b[n];
int c[n + 5];
...
}
~~~

局部数组的坏处：

1) 不会自动清零
里面是“随机值/垃圾值”，不手动初始化就可能出错。
2) 开太大容易发生错误
例如开到几十万、几百万时，可能直接运行出错（RE）。

强烈建议同学们在竞赛当中使用全局数组！



3.3 数组的输入



数组题基本都要先把数据读进数组。最常见有两种读法：下标从 $0$ 开始、下标从 $1$ 开始。

---



3.3.1 下标从 $0$ 开始



元素范围：$a[0]\sim a[n-1]$

~~~cpp
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
~~~

---



3.3.2 下标从 $1$ 开始



元素范围：$a[1]\sim a[n]$
注意：需要保证数组开得足够大，一般开到 $n+5$ 更安全。

~~~cpp
int n;
cin >> n;
for (int i = 1; i <= n; i++){
cin >> a[i];
}
~~~

优点：有些题用“第 $1$ 个到第 $n$ 个”时更直观。
注意：要小心别访问到 $a[0]$ 或 $a[n+1]$。

---



3.3.3 输入数组时的常见细节



1) 先读 $n$ 再读数组
2) 循环边界不要写错

• $0$ 开始：i < n
• $1$ 开始：i <= n

3) 数组要开够大
例如 $n\le 2\times 10^5$：

~~~cpp
const int N = 200000 + 5;
int a[N];
~~~

---



3.3.4 示例



其中，$a$ 数组的下标从 $0$ 开始，$b$ 数组的下标从 $1$ 开始（请注意区分)

~~~cpp
#include <bits/stdc++.h>
using namespace std;

const int N = 200000 + 5;
int a[N];
int b[N];

int main() {
int n;
cin >> n;

for (int i = 0; i < n; i++){
cin >> a[i];
}

for (int i = 0; i < n; i++) {
cout << a[i] << " ";
}

for (int i = 1; i <= n; i++){
cin >> b[i];
}

for (int i = 1; i <= n; i++) {
cout << b[i] << " ";
}
return 0;
}
~~~

---



4. 数组的初始化





4.1 全局数组默认初始化为 $0$



~~~cpp
const int N = 10;
int a[N]; // 全局：默认全是 0
~~~



4.2 局部数组必须手动初始化（否则是垃圾值）



最常用的两种方式：

方式 $1$：循环赋值

~~~cpp
int a[10];
for (int i = 0; i < 10; i++) a[i] = 0;
~~~

方式 $2$：用 {0} 快速清零

~~~cpp
int a[10] = {0}; // 局部也能全部变成 0
~~~



4.3 指定部分初值，剩下自动补 $0$



~~~cpp
int a[6] = {1, 2, 3}; // 后面自动补 0
~~~



4.4 初始化函数



作为拓展，后续我们常常会使用 $\text{memset()}$ 函数来初始化数组



4.4.1 基本用法



$\text{memset(地址, 值, 字节数)}$
它会把从“地址”开始的连续内存，一共“字节数”这么多字节，都设置成同一个“值”。

最常见写法（把整个数组清零）：

~~~cpp
int a[1000];
memset(a, 0, sizeof(a)); // 把 a 的所有字节都设为 0，其中 sizeof(a) 会返回 a 数组所占的字节数
~~~



4.4.2 适用范围



$\text{memset()}$ 适合初始化：

• char 数组（字符串等）
• int 数组清零（设为 0）
• long long 数组清零（设为 0）
• bool 数组清零（设为 0）
• int 数组设置成极大值/极小值



4.4.3 常见用法示例



1）清零：

~~~cpp
int a[1000];
memset(a, 0, sizeof(a));
~~~

2）把 char 数组变成全 'A'（注意这里填的是字符的 ASCII 值）：

~~~cpp
char s[10];
memset(s, 'A', sizeof(s)); // 每个位置都是 'A'
~~~

3）把 int 数组初始化为 -1：

~~~cpp
int a[1000];
memset(a, -1, sizeof(a)); // 常用于“未访问/不存在”的标记
~~~

4）把 int 数组初始化为极大值：



int a[1000];
memset(a, 0x3f , sizeof(a));  // 其意义是把 int 的4个字节全部变成0011 1111，也就是把所有值变成0011 1111 0011 1111 0011 1111 0011 1111 (B)
cout << a[0]; // a[0] = 1061109567



5）把int 数组初始化为极小值：



int a[1000];
memset(a, -0x3f , sizeof(a));  // 其意义是把 int 的4个字节全部变成1011 1111，也就是把所有值变成1011 1111 1011 1111 1011 1111 1011 1111 (B)
cout << a[0]; // a[0] = -1044266559





4.4.4 重要注意事项



1) $\text{memset()}$ 是按“字节”填充，不是按“整数”填充。
所以除了 $0$ 和 $-1$ 这种非常特殊的值以外，不要用 memset 给 int 数组设置成 1、2、100 之类。

例如（错误示例）：

~~~cpp
int a[5];
memset(a, 1, sizeof(a)); // 错！不会得到 a[i]=1，而是变成0000 0001 0000 0001 0000 0001 0000 0001 (B)
cout << a[0];// a[0] = 16843009
~~~

原因：每个字节都变成 1，最后 int 里的值会变成一个很大的数，不是 1。

2) 如果你想把 int 数组设成某个普通数字（比如全设为 5），请用循环：

~~~cpp
int a[1000];
for (int i = 0; i < 1000; i++) a[i] = 5;
~~~



4.4.5 头文件



使用 $\text{memset()}$ 需要包含：

• #include <cstring>（或者使用万能头文件 #include <bits/stdc++.h> ）



5. 数组的用处



数组的核心价值：



当你要处理“很多个同类型的数据”，并且这些数据要按顺序 / 按编号访问时，用数组最方便。



------



5.1 存一堆数据，后面反复用



很多题都会先给你 $n$ 个数，接下来要你做很多操作：求最大值、求和、排序、统计……
如果不存起来，你就只能“读一个算一个”，很多操作做不了。

例题：

A82859.数组逆序重放

A29930.合唱队形

A30707.【一维数组】【入门】计算书费

A66.陶陶摘苹果



5.2 快速按下标访问



数组最大的优势之一：

想看第 $i$ 个元素，直接访问 a[i]即可。

这在需要“频繁访问某个位置”的题里非常重要。

例题：

A82868.向量点积计算



5.3 统计出现次数



你可以用数组当“桶”：

• cnt[x] 表示数字 $x$ 出现了多少次