c++信息学竞赛数组大小规划与避坑速查表
5888
在信息学竞赛（OI）中，数组开多大是一个非常有讲究的技术活。开小了会导致运行错误（RE），开大了会导致内存超限（MLE），而开在局部变量里还可能导致栈溢出。
信息学竞赛数组大小规划与避坑速查表
一、 常见题型数组大小速查表
在竞赛中，数组大小通常遵循一个黄金法则：题目给定的最大数据范围 + 5（或 10）。
题目数据规模 (NNN)
推荐数组大小
适用场景与备注
N≤100N \le 100N≤100
arr[105]
小数据，开大点防越界即可
N≤1,000N \le 1,000N≤1,000
arr[1005]
常见二维DP或图论题，留足余量
N≤105N \le 10^5N≤105
arr[100005]
竞赛最常见规模，如排序、搜索
N≤106N \le 10^6N≤106
arr[1000010]
大数组，需注意内存占用
值域 ≤107\le 10^7≤107
arr[10000010]
桶排序、计数排序、标记数组等
二、 内存安全与存放位置（极其重要）
在 C++ 中，数组定义的位置直接决定了它的最大可用空间：
局部变量（定义在 main 函数内部）
存放区域：栈区（Stack）。
空间限制 ：通常只有 1~2MB。
极限大小 ：int 类型数组最多只能开到约 5×1055 \times 10^55×105（即 a[500005]），超过这个值极易导致栈溢出（爆栈），引发运行错误。
全局变量（定义在 main 函数外部）
存放区域：静态存储区（Data Segment）。
空间限制：受限于竞赛题目的总内存限制（通常为 128MB 或 256MB）。
极限大小 ：在 128MB 限制下，int 类型数组理论上最大可开到约 3.3×1073.3 \times 10^73.3×107。
竞赛铁律 ：大数组必须声明为全局变量！ 此外，全局数组系统会自动初始化为 0，省去了手动初始化的麻烦。
三、 进阶处理：当数组实在开不下怎么办？
如果遇到极端情况，静态数组无法满足需求，可以采用以下策略：
使用 STL 容器 ：优先使用 vector。它的数据分配在堆上，栈仅存元信息，无栈溢出风险，且支持动态扩容。
动态内存分配 ：使用 new 或 malloc 在堆上分配数组，用完记得 delete 或 free 释放，防止内存泄漏。
离散化 ：当数据范围极大（如 10910^9109）但实际元素个数不多（如 10510^5105）时，使用 vector 配合 sort 和 unique 进行离散化映射，大幅降低空间消耗。
四、 常见内存报错（RE / MLE）速查
错误类型
常见原因
解决方案
RE (运行错误)
1. 数组开太小，越界访问2. 局部大数组导致栈溢出
1. 数组大小 = 最大值 + 52. 将大数组移至全局变量
MLE (内存超限)
1. 盲目开超大数组2. 多个大数组同时存在
1. 精确计算所需空间2. 改用 vector 或离散化
总结 ：做题时先看数据范围，按"最大值+5"的原则开数组；如果是大数组，一律放在全局变量区；遇到极端大数据，果断上 vector 或离散化。