NOIP学习小站前面的例题，特别是循环结构中的例题，涉及到读取大量的数据进行处理，但都是读入数据保存到变量后立即使用变量处理数据，处理结束后也不再使用这些数据了，所以往往在循环体中都是将数据输入到同一个变量就行。但是有时候，我们读入若干数据后，还需要将这些数据都保存下来，以便于后面再次使用。这个时候如果数据量少还好处理，但是数据多的话使用很多变量来存储每一个数据是不现实的，幸好C++中有一个强有力的工具——数组，使用数组能够很好地解决上述问题。
一、引子
回看前面的一个例题，计算输入的\(n\)个整数的最小值，使用“打擂台”的方式，将最小值存放到变量\(min\)中，利用\(n\)次循环，每次输入一个整数\(m\)，输入后和\(min\)打擂并将新的最小值保存到\(min\)中。可见每输入一个整数\(m\)，就能立即处理，处理后本次输入的\(m\)就没有任何作用了。对于这个问题，我们不需要想办法把所有输入的整数都保存下来：
#include<iostream>
using namespace std;
int main()
{
int n,m,min;
cin>>n;
for(int i=1;i<=n;i++){
//每次输入的整数都放在变量m中，会自动覆盖掉上次输入的数（也保存在m中）
//因为每次处理完输入的整数后，这个数后面不会再用到，可以丢弃
cin>>m;
//第一个数 或者 m比最小值小
if(i==1 || m<min) min = m;
}
cout<<min;
return 0;
} 再来看另外一个例题：输入10个整数，计算所有整数的平均值\(avg\)，输出10个整数中比平均值\(avg\)小的数。不难得出程序的框架：
#include<iostream>
using namespace std;
int main()
{
int m;
double avg = 0;
for(int i=1;i<=10;i++){
cin>>m;
avg += m;
}
avg /= 10;
//接下来需要从10个输入的整数中找出小于avg的数
//但是现在只有最后一个输入的数保存在m中，其它数都已经被丢弃了
return 0;
} 很显然，我们需要想办法将输入的10个整数都保存下来，计算了平均之后，再将保存下来的10个整数和平均值比较。现在的问题是，如何保存这10个整数呢？用10个变量？只能说可行但是很不方便，如果问题规模扩大，要处理100个整数，难道要手写100个变量、100个几乎相同的处理过程，显然是不可取的。如果是输入\(n\)个整数，输出\(n\)个整数中小于平均值的所有整数，那么要“动态地定义\(n\)个变量”，这是无法实现的。
二、数组的用途
要解决前面的问题，简而言之就是需要有一种高效的方法，能够存储若干的数据，并且还能将每个数据取出来使用。C++中的数组就具备这样的功能。借助数组，可以在内存中开辟足够的连续的存储空间，将大量相同数据类型的数据存储到数组内部，并且又能像使用单个变量一样的方式去取出存储在数组中的数据参加运算，还能对存储在数组中的数据重新赋值。存储在数组中的每个数据称为数组的元素。
三、数组的使用方法
解决问题时，数据的规模一般是已知的，所以要借助数组保存的数据的个数（或者说最大个数）是已知的。使用数组就像使用变量一样，需要先定义，再使用。
1.数组的定义
（一维）数组的定义方式是： 数组类型 数组变量名称[元素数量];，例如：
int a[10]; //定义了一个名为a、一共有10个int类型元素的数组 long long b[100],c[1000]; double arr[100001]; char str[1001];
一句简单的定义，就已经将数组的核心内容完全体现了：
- 数组也是一种特殊的变量，所以定义中有数组变量名称；
- 数组中的所有元素都必须是相同的数据类型，定义中有数组类型，体现了数组中每个元素的数据类型；
- 数组中可以存储很多相同数据类型的元素，在定义时需要指定元素的数量，也称为数组的长度。特别注意的是，竞赛编程定义数组时，数组的长度（也就是[]中的内容）一般设置成常量（字面常量或符号常量）。
在定义数组的时候，甚至还可以为数组的每个元素赋初值：
int a[10] = {1,2,3,4,5,6,7,8,9,10};定义并初始化数组，可以省略长度，此时数组长度会被自动设置成初始化语句中数组元素的数量。
int a[] = {1,2,3,4,5,6,7,8,9,10}; 2.数组元素的使用
使用数组，一般是使用数组中的元素，这些元素就像普通的变量一样，可以为其赋值，可以参加运算，可以将数据输入到数组的某个元素中。只不过由于它们是数组的元素，所以书写的时候比起前面普通变量的书写要特殊一些。例如int a[5];，定义了一个名称为a、拥有5个int类型元素的数组。数组a中的元素的书写方法如下：
| 第1个元素 | 第2个元素 | 第3个元素 | 第4个元素 | 第5个元素 |
| a[0] | a[1] | a[2] | a[3] | a[4] |
上面书写数组元素时，[]号中的内容称为下标。可见数组中元素的使用方法是：数组名[下标]。并且数组的下标从0开始，最后一个下标应该是数组长度-1。正是因为数组下标从0开始，所以我们以后描述数组的元素，一般这样来：
| 第0个元素 | 第1个元素 | 第2个元素 | 第3个元素 | 第4个元素 |
| a[0] | a[1] | a[2] | a[3] | a[4] |
前面已经提出，数组的元素就是数组内的特殊“变量”，变量怎么用，数组的元素就能怎么用，就是书写时要用数组名[下标]的特殊形式：
int x,y,z; x = 123; y = x-1; cin>>z; cout<<x<<endl; cout<<x+y+z<<endl;
int a[10]; a[0] = 123; a[1] = a[0]-1; cin>>a[2]; cout<<a[0]<<endl; cout<<a[0]+a[1]+a[2]<<endl;
回到前面的问题，现在我们可以将10个输入的整数存放到数组中解决问题了：
#include<iostream>
using namespace std;
int main()
{
int a[10];
double avg = 0;
for(int i=0;i<10;i++){
cin>>a[i]; //第i个数输入到数组元素a[i]中
avg += a[i];
}
avg /= 10;
for(int i=0;i<10;i++){
if(a[i]<avg){ //判断已经存储到数组的第i个元素a[i]是否小于avg
cout<<a[i]<<" ";
}
}
return 0;
} 这里理解起来有一点难度，但是将循环“翻译”成顺序结构就容易理解了：
cin>>a[0]; avg += a[0]; cin>>a[1]; avg += a[1]; //... cin>>a[9]; avg += a[9];
if(a[0]<avg) {
cout<<a[0]<<" ";
}
if(a[1]<avg){
cout<<a[1]<<" ";
}
//...
if(a[2]<avg){
cout<<a[2]<<" ";
}从上面的例子可以看出，数组元素的使用往往是结合循环来批量处理的。在循环体中我们会用类似这样的功能性语句来描述：使用数组的第i个元素a[i]完成什么操作。还要特别注意循环体初值（一般用0）、终值（一般是数组元素数量-1）与数组下标的关系！
要使用数组的第i个元素，直接使用a[i]就行，非常简单高效，这样的存取方式称为“随机存取”，也就是可以通过仅仅一次基本语句操作就能对一堆数据中指定序号的那个数进行存取操作（取出值、存入新值）。数组是典型的随机存取结构。
注意：定义数组和使用数组元素都使用了[]，但定义数组的时候[]中的内容是常量，指明数组的长度；使用数组元素的时候[]中是下标，可以是常量，也可以是变量，并且往往是循环的控制变量。此外要注意下标是变量的时候，在运算的过程中要避免下标溢出（出现负数或者等于或超出了数组元素的数量）。
此外，数组的元素在内存中是连续存储的，所以使用数组比起手写若干变量解决问题，不仅仅是编程更加简洁方便，而且程序的执行效率也更高！
四、竞赛时数组使用技巧
1.使用全局数组
竞赛往往要借助数组处理大量的数据，这个时候数组需要“开”很大（定义数组时数组的长度值很大），为了避免开大数组的程序运行时被操作系统拒绝分配内存出现运行时错误，可以将数组定义为全局数组。具体方法是将数组的定义语句放到main函数的外部且在main函数的前面即可：
#include<iostream>
using namespace std;
int a[1000000]; //大数组建议定义成全局数组
int main()
{
return 0;
}知识点：使用全局数组，在定义全局数组后，数组的每个元素都会有默认值，例如最常用的int类型的全局数组元素的默认值是0。
2.定义数组时使用符号常量指定数组长度
在定义数组的时候，建议使用符号常量来指定数组的长度，并且在程序中要使用数组的长度的地方都用该符号常量，这样做的优势通过下面程序对比可知：
#include<iostream>
using namespace std;
//要修改数据规模，处理100个整数
int a[10]; //这里要修改
int main()
{
double avg = 0;
//下面语句要修改
for(int i=0;i<10;i++){
cin>>a[i];
avg += a[i];
}
avg /= 10; //这里要修改
//下面语句要修改
for(int i=0;i<10;i++){
if(a[i]<avg){
cout<<a[i]<<" ";
}
}
return 0;
} #include<iostream>
using namespace std;
//如果要修改数据规模，修改下面一处即可
const int N = 10; //赋值成100即可
int a[N];
int main()
{
double avg = 0;
for(int i=0;i<N;i++){
cin>>a[i];
avg += a[i];
}
avg /= N;
for(int i=0;i<N;i++){
if(a[i]<avg){
cout<<a[i]<<" ";
}
}
return 0;
}3.为了和自然序列一致，数组长度额外+1
数组的下标从0开始，现实生活中自然序列从1开始。例如上面的问题，修改为输出小于平均值的数的序号（从1开始计数），那么就需要这样处理：
#include<iostream>
using namespace std;
const int N = 10;
int a[N];
int main()
{
double avg = 0;
for(int i=0;i<N;i++){
cin>>a[i];
avg += a[i];
}
avg /= N;
for(int i=0;i<N;i++){
if(a[i]<avg){
cout<<i+1<<" "; //下标比自然序号小1，所以输出i+1
}
}
return 0;
}像这样下标和自然序号有关联的问题，处理的时候需要格外注意。其实我们还可以“改造”一下数组，让存储数据的下标和自然序号一致。具体做法是定义数组的时候至少额外多开一个，存取数据就从数组的1号元素开始，不用0号元素：
#include<iostream>
using namespace std;
const int N = 10;
int a[N+1]; //至少额外多开1个
int main()
{
double avg = 0;
//只使用a[1]～a[N]，不使用a[0]
for(int i=1;i<=N;i++){
cin>>a[i];
avg += a[i];
}
avg /= N;
//只使用a[1]～a[N]，不使用a[0]
for(int i=1;i<=N;i++){
if(a[i]<avg){
cout<<i<<" ";
}
}
return 0;
}4.数组长度设置为数据规模最大值
将上面的问题变形：首先输入一个正整数\(n\)（\(1 \le n \le 10000\)），然后输入\(n\)个整数，计算所有整数的平均值\(avg\)，输出\(n\)个整数中比平均值\(avg\)小的数。初学者可能不假思索，写出下面的程序：
#include<iostream>
using namespace std;
int main()
{
int n;
cin>>n;
int a[n]; //不建议这样写，即使编译能通过，甚至运行也没有问题，但是有风险
double avg = 0;
for(int i=0;i<n;i++){
cin>>a[i];
avg += a[i];
}
avg /= n;
for(int i=0;i<n;i++){
if(a[i]<avg){
cout<<a[i]<<" ";
}
}
return 0;
}注意：上面的程序存在风险，前面指出定义数组的时候数组长度应该是常量，上面程序使用了变量。随着编译器的不断优化，高版本的编译器已经能够支持上面程序中那样的动态定义数组（数组的长度是一个变量），但是存在较大的风险，不推荐使用。
那么该如何处理呢？我们注意到了题目中给出了数据规模——\(1 \le n \le 10000\)，所以最多只会输入10000个整数，那么我们就按照数据规模的极限值开数组，这样肯定能满足所有情况。但是这样做有一个缺点就是如果运行时输入的\(n\)值远小于数据规模，数组大量的存储空间没有使用起来，浪费了存储空间。不过竞赛时推荐使用这样的方式，即使C++中也支持其它动态开数组的方法（感兴趣的同学可自行百度）。
#include<iostream>
using namespace std;
int a[10000]; //按照数据规模的极限值开数组
int main()
{
int n;
cin>>n;
double avg = 0;
for(int i=0;i<n;i++){
cin>>a[i];
avg += a[i];
}
avg /= n;
for(int i=0;i<n;i++){
if(a[i]<avg){
cout<<a[i]<<" ";
}
}
return 0;
}竞赛时更一般的做法是，定义数组时，在数据规模的基础上再多开几个长度（例如10个），这样可以有效避免一些边界问题！