数组

有了循环之后，你很快就会发现简单地定义一个一个的变量有点“不够用”了，比如考虑如下问题：

输入整数 $N$，然后输入 $N$ 个数的一个数列，将这个数列倒序输出。

我们想要倒序输出，就说明我们在读取完数列的最后一个整数时，还要“记住”前面的 $N-1$ 个整数，所以我们每读取到一个整数都得将其保存在变量里，但我们在预先不知道数列长度的情况下怎么知道该定义多少个变量呢？这似乎陷入了死局。

(在这里我们不考虑递归等技巧) 我们希望有一种语法，可以批量开一堆变量，而且最好能用下标去索引它们。在 C/C++ 中我们可以通过定义数组来实现这一点。我们先给出上面问题的一段示例代码：

#include <bits/stdc++.h>

int main ()
{
    int n;
    std::cin >> n;
    int a[n];
    for (int i = 0; i < n; i++)
        std::cin >> a[i];
    for (int i = n - 1; i >= 0; i--)
        std::cout << a[i] << '\n';
    return 0;
}

这里出现的新语法是 int a[n]。如果说 int 类型的变量是一个可以存放一个整数的小盒子，那么 int a[n] 就定义了 $n$ 个小盒子，每个小盒子都可以存放一个整数。值得注意的是，这里的“小盒子”是按照 $0,1,\cdots, n-1$ 编号的。

如果上面关于 VLA 的内容你没有看懂，没有关系，一句话概括就是使用变量作为数组的长度“不太好”。我们的 OJ 题会对输入数据的范围作出严格的限制，你可以根据数据范围将数组开到足够大的一个固定长度。假设题目规定了 $N\leq 1000$，那么一个不使用 VLA 的程序应该这样写：

#include <bits/stdc++.h>

int a[1000];

int main ()
{
    int n;
    std::cin >> n;
    for (int i = 0; i < n; i++)
        std::cin >> a[i];
    for (int i = n - 1; i >= 0; i--)
        std::cout << a[i] << '\n';
    return 0;
}

这里我们希望不加解释地做出一个规定：如果你要定义一个定长的数组，请将它定义在 main() 函数的外面。

#include <bits/stdc++.h>
int main () { char s[1 << 25]; }

如果你没有看懂这段话，那就老老实实地遵守我们的规定吧。

总有一些“完美主义者”觉得这样写代码十分令人不爽——如果 $N$ 远小于 1000，我们的代码岂不是无谓的多使用了很多资源？这里我们再介绍一种定义数组的方式，它在功能上和前面的几种是完全相同的：

#include <bits/stdc++.h>

int main ()
{
    int n;
    std::cin >> n;
    int *a = new int [n];
    for (int i = 0; i < n; i++)
        std::cin >> a[i];
    for (int i = n - 1; i >= 0; i--)
        std::cout << a[i] << '\n';
    delete [] a;
    return 0;
}

int *a = new int [n] 的功能是定义一个长度为 $n$ 的数组，每个数组元素都是 int 类型，这个数组的名字叫做 a。我们在这里希望强调一点：如果你使用了new语法定义数组，请一定在你确定不会再使用该数组的时刻 (例如 return 0 之前) 使用delete释放它。