机试环境：IO 速度与内存边界

场景引入

同一份代码，小数据跑得好好的，换成大数据就超时；或者在本地跑得好好的，交上去直接崩了。算法复杂度算过没问题，题也做对了，失分来自程序之外的东西——读入速度、栈空间、数组容量。

这些是考场环境给的约束。它们的数值都能提前估出来，估一次就能用一辈子。

一、`cin` 慢在哪，怎么让它不慢

C++ 的 cin/cout 默认和 C 的 scanf/printf 保持同步：两套 IO 可以随意混用，输出顺序不会乱。这个保证是有代价的，同步机制让每次读写都多绕了一层。

数据量小的时候感觉不出来。到了十万行以上的输入，这层开销会累积成实打实的耗时。

解绑的写法是两行，放在 main 的最开头：

cpp

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // ...
}

第一行断开与 C stdio 的同步
第二行断开 cin 与 cout 的绑定（默认每次读之前会先刷新 cout，交互题之外用不上）

解绑之后有一个代价：不能再混用 scanf/printf。 同步没了，两套缓冲区各走各的，输出顺序会乱掉。所以选一套用到底：要么全 cin/cout 加解绑，要么全 scanf/printf 不解绑。

scanf/printf 本身就够快，不需要额外设置。拿不准就用 scanf/printf，少两行代码也少一个坑。

二、时间够不够，先估一下

评测机每秒能跑多少次简单运算，是个经验量级——通常按 一亿次 来估，然后看题目的时限。

估的方法是把复杂度里的 n 代入题面给的数据范围：

n 是 1e5，O(n²) 就是 1e10 次，稳超；O(n log n) 约 1.7e6 次，绰绰有余
n 是 5000，O(n²) 是 2.5e7 次，能过
n 是 20，O(2ⁿ) 是一百万，能过；n 是 40 就不行了

题面给的数据范围本身就是提示。 出题人把 n 定在 5000 而不是 1e5，多半是在告诉你 O(n²) 可以接受。这一点在拿不准该用哪种解法时很有用——先看范围，再决定要不要费劲去想更优的做法。

三、数组该开多大

按题面的数据范围上限开，再留一点余量。

const int MAXN = 100005;    // 题面说 n ≤ 1e5，多开几个
int a[MAXN];

多开的那几个是给边界留的。下标从 1 开始计数时会用到 a[n]，某些算法要访问 a[n+1] 作为哨兵，差一个就越界。越界读通常读到垃圾值，越界写会破坏相邻变量，两种都很难调。

二维数组要算乘积。g[1005][1005] 的 int 数组是 1005 × 1005 × 4 字节，约 4MB；开到 g[5005][5005] 就是 100MB，多数题的内存限制放不下。

估算内存时用这几个数：

类型	字节	一百万个
`char` / `bool`	1	1MB
`int` / `float`	4	4MB
`long long` / `double`	8	8MB

标记数组用 bool 而不是 int，内存直接省到四分之一。

四、大数组放全局，别放局部

这一条是崩溃类失分的主要来源。

int main() {
    int a[1000000];    // 4MB 放在栈上
    // ...
}

局部变量在栈上分配，而栈空间通常不大——常见的默认值在 1MB 到 8MB 这个量级。一个 4MB 的局部数组就可能直接把栈撑爆，表现是程序还没开始跑就崩了。

全局变量（和 static 变量）在静态区，容量按题目的内存限制算，几十 MB 都没问题：

int a[1000000];        // 放在函数外面

int main() {
    // ...
}

还有一个附带的好处：全局数组会被自动初始化为 0，局部数组不会——局部数组里是未初始化的垃圾值，忘了清零同样会出错。

机试里的默认做法是把大数组一律定义在全局。 需要每组数据重新清零时用 memset，见多组数据那一篇。

五、递归能有多深

递归的每一层都要在栈上放一个栈帧，装局部变量和返回地址。层数太多，栈同样会爆。

具体能递归多少层取决于每层用了多少栈空间——层里的局部变量越多越少，几十万层是一个需要开始警惕的量级。

会撞上这条线的典型场景：

链表长度 1e5 还用递归遍历
树退化成一条链（比如按升序插入建出来的二叉搜索树），递归深度等于节点数
图的 DFS 遇到一条长链

对策是把递归改写成迭代，用自己的栈或者队列替代系统栈。链表反转、二叉树遍历、图的 DFS 都有成熟的迭代写法，本站对应的章节里都给了。

六、几个和环境有关的小事

memset 不是万能的赋值。 它按字节填充，所以 memset(a, 0, ...) 和 memset(a, -1, ...) 是对的（0x00 和 0xFF 重复四遍还是 0 和 -1），memset(a, 1, ...) 得到的每个 int 是 0x01010101 而不是 1。要填别的值就老实写循环。

清零只清用到的部分。 数组开了 1e6 但这组数据只用到前 n 个时，memset(a, 0, sizeof(int) * (n + 1)) 比整块清快得多。多组数据的题里，整块清有时本身就会超时。

本地能跑不代表评测机能跑。 编译器版本、栈大小、优化选项都可能不一样。栈这一项差异尤其大，所以「本地正常、交上去崩」时，先怀疑局部大数组和递归深度。

机试环境：IO 速度与内存边界 ​

场景引入 ​

一、cin 慢在哪，怎么让它不慢 ​

二、时间够不够，先估一下 ​

三、数组该开多大 ​

四、大数组放全局，别放局部 ​

五、递归能有多深 ​

六、几个和环境有关的小事 ​

延伸阅读 ​