“Time Limit Exceeded” 这几个红字很多写 C 语言的人第一次见到它是在某个在线评测页面上本地样例跑得飞快一提交就被打回来刷新好几次结果都一样。这几乎是每个刚接触 OJ 的人必过的一关尤其是 C 语言这种把细节全部暴露给你的语言超时往往不是“答案算错了”而是“答案算得太慢”。有人贴出一整屏代码求指点评论区一句“复杂度超了”就打发了可复杂度到底怎么估、常数因子怎么砍、输入输出能省多少时间很少有人讲透。这篇内容就把 C 语言 OJ 系统超时这件事拆开讲。从评测机那 1 秒到底在数什么到拿到题目怎么根据数据范围倒推算法再到输入输出、数组初始化、容器选择、递归写法这些具体位置上的时间黑洞最后给一份可以直接照着排查的清单。适合两类人一类是答案逻辑没问题但总卡时间的另一类是还没养成“先看数据范围再动手”习惯的。文中所有的代码片段都可以直接编译运行实测数据是我自己在不同机器上反复跑出来的数量级参考不是凭空估的。1. 先搞清楚评测机那 1 秒到底在数什么1.1 时间限制的真实含义大多数人以为提交之后评测机会把代码跑一遍跑多久算多久超过 1000 毫秒就判超时。这个理解大体对但中间有几层容易被忽略的细节。评测机通常记录的是程序的 CPU 时间而不是你在本地感觉到的“钟表时间”所以你在自己电脑上一边开浏览器一边跑跑出来 1.3 秒实际提交可能过也可能更糟——因为评测机的 CPU 主频、编译器版本、编译优化级别都和你本地不一样。更要命的是评测机同时可能在跑别人的题目机器负载高的时候同样的代码耗时会有波动。所以业内的经验做法是不要在 1 秒的题上写出“刚好 1 秒”的代码要给自己留出至少三到五倍的余量。也就是说一道限时 1000ms 的题你的目标应该是把最坏情况的运算量压到 200ms 到 300ms 对应的级别这样不管机器怎么抖都不会翻车。那么 1 秒大概对应多少次基本操作这个数在不同资料里说法不一我给一个自己反复验证过的区间现代评测机上一秒钟大致能做 1e8 到 3e8 次“带数组访问的简单循环迭代”。所谓“简单循环迭代”指的是像自增、比较、一次数组读取、一次加法这种量级的操作。如果你的循环体内有取模、除法、函数调用、内存分配这个数字要往下调可能只有 3e7 到 5e7。这个经验值非常关键因为它是你把“数据范围”翻译成“能不能过”的换算系数。很多人的代码思路完全正确就是没有做这一步换算写完就交交了就看红字。1.2 为什么“本地跑得飞快”提交就超时本地和评测机的差异主要来自四个地方我按踩坑频率排个序。第一个是编译选项。你在本地可能用 IDE 默认的 Debug 模式编译那种模式下很多编译器会把循环展开、内联优化全关掉跑得反而慢但反过来评测机常见的编译选项是开一定程度的优化你的代码会变快。这两个方向都有如果本地慢评测机快那说明你本地的代码还有优化空间值得庆幸如果本地快评测机慢多半是本地数据太弱压根没触发最坏情况。第二个是测试数据的强度。这是超时的头号原因。你本地测的是题目给的样例样例往往只有五六行数据n 是 5 或者 10。真正的测试点里 n 可能是 1e5你的代码在 n5 时耗时 0 毫秒在 n1e5 时可能就是十秒钟。所以永远不要用样例来判断自己会不会超时要看题目描述里那个数据范围。第三个是机器差异。这个没什么好办法只能靠留余量。有些人习惯在本地用最弱的配置测比如老笔记本这反而是一种自我加压的好习惯。第四个是无意识的复杂度放大。比如你在循环里调用了strlen、在循环里做了vector的push_back而没预留空间、在每组测试数据里都memset一个巨大的数组。这些在 n 小的时候完全看不出来n 一大就原形毕露。提示判断自己会不会超时不要看运行时间要看“我的算法做了多少次最内层操作”。这个数字比秒数靠谱得多。2. 拿到题目先看数据范围复杂度对照表2.1 n 的大小决定了你能写什么算法我在做题时的第一件事永远不是想算法是翻到题目最后看数据范围。这一步花十秒钟能省掉半小时的返工。下面这张表是我自己用的对照表左边是 n 的规模右边是这个规模下能通过的复杂度上限换算基准按 1e8 次简单操作每秒算。数据规模 n可接受的复杂度典型算法举例n ≤ 10O(n!) 或 O(2^n)全排列枚举、暴力搜索n ≤ 20O(2^n)状态压缩、子集枚举n ≤ 100O(n^3)三重循环、简单区间 DPn ≤ 1000O(n^2)二维 DP、朴素最短路n ≤ 1e5O(n log n)排序、二分、堆、树状数组n ≤ 1e6O(n) 且常数小线性扫描、前缀和、双指针n ≤ 1e7O(n) 且必须做 I/O 优化快读、逐字节处理用这张表的方式很直接题目说 n ≤ 1e5那就意味着 O(n^2) 的写法大约是 1e10 次操作必死不管你的代码写得多精简。这时候你要么换算法要么想清楚有没有 O(n log n) 或者 O(n) 的做法。我见过太多这样的情况题目是“给定一个长度为 n 的数组q 次询问区间和”n 和 q 都是 1e5有人写了个双层循环每组询问都从头加到尾。这个代码在样例上n6, q3跑得完美提交之后必然超时因为最坏情况是 1e5 × 1e5 1e10 次加法。标准解法是前缀和预处理 O(n)每次询问 O(1)总复杂度 O(n q)。这个转化过程没有任何技巧含量纯粹是“看范围选工具”。2.2 常数因子是被低估的第二道坎复杂度对了也可能超时这是新手最难接受的一点。O(n) 的代码跑 1e6 的数据有人跑 5 毫秒有人跑 400 毫秒差距全在常数上。什么会放大常数内存访问的局部性排在前面。二维数组按行访问和按列访问在 n2000 的时候能差出三到五倍的耗时因为按列访问会让 CPU 缓存反复失效。这不是玄学是硬件层面的事缓存行一次加载 64 字节你按行访问时这些数据马上都能用上按列访问时每次只能用到其中 4 个字节剩下的都被浪费了。函数调用也算。一个被调用 1e7 次的函数哪怕函数体只有一行调用开销本身就够呛。C 语言里做小函数建议加static inline让编译器有机会内联尤其在评测机开了优化的情况下效果明显。当然如果你本地编译没开优化加不加可能看不出差别但提交上去是有区别的。取模和除法比加减乘慢一个数量级。在需要大量取模的题里比如计数类问题能合并的取模就合并能用位运算代替的比如对 2 的幂取模就用位运算。这一条在 n 到 1e7 的时候才会体现出来n 小的时候不用管。还有读写内存的模式。频繁malloc和free是灾难vector不预留空间导致的反复扩容也是灾难——每次扩容都要把老数据全部复制一遍1e6 个元素如果扩容二十次复制的总量是千万级。养成习惯知道大概要放多少元素就先reserve一下。3. 输入输出最容易被忽视的时间黑洞3.1 scanf 与 cin 的真实差距纯 C 的scanf在绝大多数场景下是够用的1e5 级别的输入毫无压力1e6 级别也能扛。真正会出问题的是两个地方一是用 C 的cin而又没关同步二是在超大输入1e6 以上下还要用格式化输出。cin默认和 C 的 stdio 保持同步这个机制是为了让你能混用cin和scanf而不出错代价是每次读写都要过一遍同步检查。解决办法是在main开头加两行ios::sync_with_stdio(false); cin.tie(nullptr);加了之后cin的速度能追平甚至超过scanf。但有个坑必须记住关掉同步之后cin和scanf绝对不能混用混用的结果是输入顺序错乱表现出来就是“答案莫名其妙不对”而且极难排查因为代码逻辑看起来毫无问题。还有一个更隐蔽的endl。endl不只是输出一个换行符它还会强制刷新缓冲区。在循环里用cout x endl输出 1e5 个数每一次都触发一次系统调用级别的刷新慢得离谱。换成\n就没事了。这个坑我踩过一个只需要输出 1e5 行的题把endl换成\n之后从超时变成了 60 毫秒。3.2 手写快读与批量输出的写法当输入规模到 1e6 甚至 1e7scanf也开始吃力了这时候要上快读。原理很简单getchar逐字符读比scanf的格式解析快因为省掉了格式串的解析开销。#include stdio.h static inline int readInt(void) { int c getchar(), x 0, f 1; while (c ! EOF (c 0 || c 9)) { if (c -) f -1; c getchar(); } if (c EOF) return 0; while (c 0 c 9) { x x * 10 (c - 0); c getchar(); } return x * f; }这段代码有几个细节值得说。c声明成int而不是char因为getchar在文件结束时返回EOF通常是 -1char类型在某些平台上是有符号的比较时可能出问题。循环里的EOF判断不能省否则读到输入末尾会死循环表现出来还是超时但原因完全不同。负数处理用f标记避免对-2147483648取反溢出。输出端同理如果题目要输出 1e6 个数逐个printf也是有成本的。可以自己攒缓冲区static char obuf[1 20]; static int olen 0; static inline void writeInt(int x) { if (x 0) { obuf[olen] 0; return; } if (x 0) { obuf[olen] -; x -x; } char tmp[12]; int t 0; while (x) { tmp[t] (char)(0 x % 10); x / 10; } while (t) obuf[olen] tmp[--t]; }最后在main返回前fwrite(obuf, 1, olen, stdout);一次性刷出去。缓冲区大小设成 1 到 4 MB 都行注意别超过题目可能的内存限制。这套写法在 1e6 级别的输出上比printf快三到五倍实测过很多次。注意手写快读只在真的需要的时候用。1e5 以内的输入scanf完全够写快读反而增加出错概率。而且快读代码里如果漏了负号、漏了 EOF 判断调试成本很高。3.3 多组数据下的 I/O 细节多组测试数据的题有个固定套路读入通常写成while (scanf(%d, n) ! EOF) { /* 处理 */ }或者题目明确给了组数 T那就scanf(%d, T); while (T--) { ... }。这两种写法本身没问题问题出在“每组数据处理完要清理状态”这件事上。如果每组数据都要把一个大数组清零而 T 又很大这部分开销会累积。有个常见做法是用一个“访问标记数组”加时间戳代替每次都memsetint vis[N], stamp[N], cur 0; /* 每组数据开始时 */ cur; /* 判断是否访问过 */ if (stamp[u] ! cur) { stamp[u] cur; vis[u] 0; }这样每次“清空”的成本从 O(N) 降到 O(1)只在真正访问到某个位置时才初始化。这个技巧在 T 很大、N 也很大、但每组数据实际用到的元素很少的场景下效果极其明显。4. 算法与数据结构层面的典型陷阱4.1 循环里反复算同一个东西这是最普遍的超时原因之一而且极其隐蔽因为代码看起来“没错”。最经典的是strlen/* 慢每次循环都重新数一遍长度 */ for (int i 0; i strlen(s); i) { /* ... */ }strlen是 O(n) 的放在循环条件里就变成了 O(n^2)。字符串长度 1e5 的时候这就是 1e10 次字符扫描必死。改成先取长度int len strlen(s); for (int i 0; i len; i) { /* ... */ }类似的还有在循环里反复算pow(2, i)、反复算数组长度、反复调用一个返回常量的函数。这些东西编译器有时候能帮你优化掉有时候不能不要赌。还有一种变体是在双层循环里做不必要的重复计算。比如求两两之间的某种值内层循环里每次都重新算一遍a[i] * a[i]完全可以提到外层。这类优化的收益可能只有百分之二三十但在卡时间的边缘情况下就是生与死的区别。4.2 初始化开销memset 与容器的反复构造memset本身很快一个 1e6 的int数组清零也就一两毫秒。但如果你有 1e4 组测试数据每组都清零一个 1e6 的数组那就是 1e10 字节的写入妥妥超时。判断标准很简单算一下“清零总字节数”超过 1e8 就要警惕。解决办法有三种。一是缩小数组看能不能只清实际用到的部分。二是用上面说的时间戳技巧。三是把数组开在全局全局数组在程序启动时已经被清零一次如果题目只有一组数据连memset都不用写。容器这边的问题主要在vector和map。vector不预留空间会反复扩容扩容时要把已有元素全部复制到新内存1e6 个元素扩容约 20 次复制总量是 O(n) 的两倍左右虽然渐进复杂度没变但常数上去了。养成v.reserve(n)的习惯成本几乎为零。map是红黑树每次操作 O(log n) 且常数不小1e6 次插入可能要好几秒。如果键的范围可控比如都是 1 到 1e6 的整数直接用数组当哈希表速度能快一个数量级。unordered_map好一些但仍有哈希计算和链表遍历的开销而且某些实现下会被特殊数据卡成 O(n)。4.3 递归、容器与常数选择递归写起来清爽但每一层调用都有栈帧开销。深度到 1e5 的时候光是函数调用本身就可能吃掉几百毫秒而且还有栈溢出的风险默认栈空间通常只有几 MB。能改成迭代的尽量改尤其是线性递归。举个具体的求斐波那契数列第 n 项n 到 1e6。用朴素递归是 O(2^n)直接爆炸用带记忆化的递归是 O(n) 但每层一次函数调用用两个变量迭代是 O(n) 且没有调用开销。三者渐进复杂度后两个一样实测差距在三到五倍。再比如并查集。不写路径压缩的话最坏情况退化成链单次查询 O(n)整体 O(n^2)。加上路径压缩和按秩合并之后接近 O(1)。这个优化只多写三行代码收益巨大属于必做项。还有排序。需要排序的时候优先用标准库的qsort或者 C 的sort不要自己手写冒泡或者选择排序。手写快排如果基准点选得不好比如固定选第一个元素遇到有序数据会退化成 O(n^2)而标准库的排序实现通常做了三数取中和小区间插入排序的优化能扛住各种刁钻数据。场景常见慢写法快写法量级差距循环里求长度for(i0;istrlen(s);i)先存lenO(n^2) → O(n)频繁插入vector不reserve先reserve(n)常数 1.5~2 倍键为小整数mapint,int直接用数组数倍到十数倍线性递归递归求第 n 项两个变量迭代3~5 倍并查集不压缩路径压缩 按秩合并O(n) → 近似 O(1)5. 一次完整的改造实录从 TLE 到 AC5.1 题目与暴力解法我拿一道很常见的题型做演示给定 n 个整数接下来 q 次询问每次给出 l 和 r输出下标从 l 到 r 的元素之和。数据范围是 n, q ≤ 100000元素绝对值不超过 1e4多组测试数据。先看暴力版本这也是绝大多数人第一反应写出来的东西#include stdio.h int a[100005]; int main(void) { int n, q; while (scanf(%d%d, n, q) ! EOF) { for (int i 1; i n; i) scanf(%d, a[i]); while (q--) { int l, r; scanf(%d%d, l, r); long long sum 0; for (int i l; i r; i) sum a[i]; printf(%lld\n, sum); } } return 0; }逻辑完全正确样例也能过。但是最坏情况——每次询问都是l1, rn——内层循环跑满 n 次总共 q × n 1e10 次加法。按每秒 1e8 到 3e8 次算需要三十秒到一百秒评测机那边直接判超时连商量的余地都没有。这里我要强调一个心态问题看到超时不要第一反应去“优化代码”比如把printf换成putchar、把int换成register。这些改动顶多省 10%而你需要省 99%。方向错了再努力也没用。5.2 定位瓶颈定位的方法很朴素算最坏情况下的内层操作次数。这道题的内层就是那个求和循环循环次数是r - l 1最坏 n。外层是 q 次询问所以是 n × q。把数据范围的数字代进去1e5 × 1e5 1e10超过预算两个数量级。下一步是问自己这 1e10 次计算里有多少是重复的答案是绝大部分。从 1 加到 100000 和从 1 加到 99999前者的结果只比后者多最后一项。但暴力写法每次都从头加把前面的工作全部重做了。这就是典型的“重复计算”型瓶颈。找到了重复优化方向就明确了把重复的部分缓存起来。前缀和就是干这个的。定义pre[i] a[1] a[2] ... a[i]那么区间和就是pre[r] - pre[l-1]一次减法搞定。预处理 O(n)每次询问 O(1)。5.3 改造后的版本与实测对比#include stdio.h static int a[100005]; static long long pre[100005]; int main(void) { int n, q; while (scanf(%d%d, n, q) ! EOF) { pre[0] 0; for (int i 1; i n; i) { scanf(%d, a[i]); pre[i] pre[i - 1] a[i]; } while (q--) { int l, r; scanf(%d%d, l, r); printf(%lld\n, pre[r] - pre[l - 1]); } } return 0; }改动只有三处多了一个pre数组、读入时顺手累加、询问时改成减法。总操作次数从 1e10 降到 1e5 1e5 2e5快了五个数量级。在我的机器上nq1e5 的单组数据暴力版本跑不完几十秒前缀和版本连读入带计算不到 20 毫秒。这里有个容易忽略的细节pre数组用了long long。因为 n 最大 1e5每个元素绝对值 1e4总和最大是 1e9这个数用int其实装得下int上限约 2.1e9但很接近了。如果题目把元素范围改成 1e9那总和会达到 1e14必须用long long。这类溢出问题在 OJ 上表现为“答案错误”而不是超时但根源是同一种思维习惯——动手前先把数值范围算一遍。再看一个和 I/O 相关的改造。假设有一道题要输出 1e6 行每行一个整数用printf(%d\n, x)循环输出。我实测过这一百万次调用大约耗时 180 到 250 毫秒取决于机器。改成上面说的缓冲区写法之后降到 40 毫秒左右。如果题目限时 1000ms 且算法本身已经吃掉 700ms这 150 毫秒的差距就是过与不过的分界线。改造项改造前耗时改造后耗时提升幅度区间求和1e5 次询问超时无法完成约 20 ms五个数量级输出 1e6 个整数约 200 ms约 40 ms约 5 倍读入 1e6 个整数scanf约 150 ms—基准读入 1e6 个整数快读—约 50 ms约 3 倍endl改\n1e5 行超时约 60 ms从不可用到可用6. 排查清单与常见问题速查6.1 提交前自查流程我现在每次提交前会过一遍下面这个流程平均花两分钟比提交之后等结果、看红字、改代码、再提交要快得多。第一步把题目描述里的数据范围抄在手边算出 n 的最大值对应可接受的复杂度和自己写的算法对一下。这一步能拦下八成必然超时的代码。第二步找最内层循环数它最多执行多少次。把 n 的最大值代进去得到总操作数除以 1e8估算秒数。超过限时的三分之一就要动手优化。第三步检查循环里有没有重复计算的东西尤其是循环条件里的函数调用以及内层循环里和外层无关的表达式。第四步检查初始化开销。多组数据的题算一下“每次清零的字节数 × 组数”超过 1e8 就要想办法。第五步检查输入输出。输入超过 1e6 或者输出格式是逐行的大量数据考虑快读和缓冲输出。第六步检查有没有可能死循环。while条件里变量的更新语句漏写、EOF判断缺失、浮点数比较用等号这些都是常客表现同样是超时。提示如果你怀疑某个循环体拖了后腿可以把它先注释掉换成固定值看运行时间的变化。这种“二分定位”的办法在几万行的代码里很有用。6.2 常见问题对照表现象最可能的原因处理方式小样例过大样例超时复杂度不够算法方向错换算法看是否能预处理或复用中间结果所有测试点都超时连小数据也是死循环或读入卡住检查while的更新、EOF判断、多组数据读入格式偶尔超时偶尔通过常数在临界点机器负载波动砍常数把操作数压到限时的三分之一以下单组数据正常多组就超时初始化开销过大用时间戳数组或缩小初始化范围改成 C 写法后更慢没关iostream同步或用了endl关同步endl换成\n输出量很大时超时逐次输出触发刷新攒缓冲区批量输出递归题超时且伴随异常退出递归过深或重复子问题改迭代或加记忆化6.3 几条用血换来的小经验第一条编译优化选项在本地和评测机可能不一样所以不要在本地测出“刚好卡线”就开始庆幸。我现在的习惯是把本地的数据规模放大到题目给定的最大值甚至再乘个两倍如果本地在这个规模下仍然只用了限时的十分之一我才敢放心提交。第二条int溢出有时候表现得像超时。比如你在一个循环里做累加溢出成负数之后导致循环条件永远成立那就是彻底的死循环。这种情况特别难查因为你看代码看不出问题要盯数值。所以涉及累加、乘法的变量先算一下理论上限。第三条测试数据的边界往往是最毒的。n 取最大值、所有元素都相同、所有询问都是同一个区间这些情况在随机数据里出现概率极低但出题人一定会放进去。所以本地测试不要只用随机生成器要手动构造这几个极端情况。第四条超时和内存超限有时候会互相转化。你为了省时间开了个巨大的数组做打表结果内存超了你把数组改小改用map结果时间又不够了。这时候要找平衡点通常的做法是把范围最大的那一维压到刚好够用不要预留太多。第五条也是我觉得最有用的一条如果你已经改了三轮还是超时停下来把算法重新想一遍而不是继续抠代码。抠常数能救回来的时间最多两三倍而换算法能带来数量级的差别。我自己的经验是第一次超时先检查常量和 I/O如果还不过直接推翻重写比在旧代码上打补丁快得多。有一次我做一道统计类题目n 是 2e5我先写了个 O(n^2) 的比较超时改成排序后二分还是超时最后发现题目要求的是“不同元素的个数”用一次线性扫描加标记数组就完事了复杂度降到 O(n)。整个过程我花了四十分钟在错误的算法上打转而正确答案只需要思考三分钟。这件事之后我就养成了习惯写代码前先在纸上写清楚复杂度和最内层操作次数哪怕只是一行字。 
长河君 · 2026/11/3 8:53:53 · 阅读 1.2k C语言OJ超时排查：从复杂度到I/O优化实战
“Time Limit Exceeded” 这几个红字很多写 C 语言的人第一次见到它是在某个在线评测页面上本地样例跑得飞快一提交就被打回来刷新好几次结果都一样。这几乎是每个刚接触 OJ 的人必过的一关尤其是 C 语言这种把细节全部暴露给你的语言超时往往不是“答案算错了”而是“答案算得太慢”。有人贴出一整屏代码求指点评论区一句“复杂度超了”就打发了可复杂度到底怎么估、常数因子怎么砍、输入输出能省多少时间很少有人讲透。这篇内容就把 C 语言 OJ 系统超时这件事拆开讲。从评测机那 1 秒到底在数什么到拿到题目怎么根据数据范围倒推算法再到输入输出、数组初始化、容器选择、递归写法这些具体位置上的时间黑洞最后给一份可以直接照着排查的清单。适合两类人一类是答案逻辑没问题但总卡时间的另一类是还没养成“先看数据范围再动手”习惯的。文中所有的代码片段都可以直接编译运行实测数据是我自己在不同机器上反复跑出来的数量级参考不是凭空估的。1. 先搞清楚评测机那 1 秒到底在数什么1.1 时间限制的真实含义大多数人以为提交之后评测机会把代码跑一遍跑多久算多久超过 1000 毫秒就判超时。这个理解大体对但中间有几层容易被忽略的细节。评测机通常记录的是程序的 CPU 时间而不是你在本地感觉到的“钟表时间”所以你在自己电脑上一边开浏览器一边跑跑出来 1.3 秒实际提交可能过也可能更糟——因为评测机的 CPU 主频、编译器版本、编译优化级别都和你本地不一样。更要命的是评测机同时可能在跑别人的题目机器负载高的时候同样的代码耗时会有波动。所以业内的经验做法是不要在 1 秒的题上写出“刚好 1 秒”的代码要给自己留出至少三到五倍的余量。也就是说一道限时 1000ms 的题你的目标应该是把最坏情况的运算量压到 200ms 到 300ms 对应的级别这样不管机器怎么抖都不会翻车。那么 1 秒大概对应多少次基本操作这个数在不同资料里说法不一我给一个自己反复验证过的区间现代评测机上一秒钟大致能做 1e8 到 3e8 次“带数组访问的简单循环迭代”。所谓“简单循环迭代”指的是像自增、比较、一次数组读取、一次加法这种量级的操作。如果你的循环体内有取模、除法、函数调用、内存分配这个数字要往下调可能只有 3e7 到 5e7。这个经验值非常关键因为它是你把“数据范围”翻译成“能不能过”的换算系数。很多人的代码思路完全正确就是没有做这一步换算写完就交交了就看红字。1.2 为什么“本地跑得飞快”提交就超时本地和评测机的差异主要来自四个地方我按踩坑频率排个序。第一个是编译选项。你在本地可能用 IDE 默认的 Debug 模式编译那种模式下很多编译器会把循环展开、内联优化全关掉跑得反而慢但反过来评测机常见的编译选项是开一定程度的优化你的代码会变快。这两个方向都有如果本地慢评测机快那说明你本地的代码还有优化空间值得庆幸如果本地快评测机慢多半是本地数据太弱压根没触发最坏情况。第二个是测试数据的强度。这是超时的头号原因。你本地测的是题目给的样例样例往往只有五六行数据n 是 5 或者 10。真正的测试点里 n 可能是 1e5你的代码在 n5 时耗时 0 毫秒在 n1e5 时可能就是十秒钟。所以永远不要用样例来判断自己会不会超时要看题目描述里那个数据范围。第三个是机器差异。这个没什么好办法只能靠留余量。有些人习惯在本地用最弱的配置测比如老笔记本这反而是一种自我加压的好习惯。第四个是无意识的复杂度放大。比如你在循环里调用了strlen、在循环里做了vector的push_back而没预留空间、在每组测试数据里都memset一个巨大的数组。这些在 n 小的时候完全看不出来n 一大就原形毕露。提示判断自己会不会超时不要看运行时间要看“我的算法做了多少次最内层操作”。这个数字比秒数靠谱得多。2. 拿到题目先看数据范围复杂度对照表2.1 n 的大小决定了你能写什么算法我在做题时的第一件事永远不是想算法是翻到题目最后看数据范围。这一步花十秒钟能省掉半小时的返工。下面这张表是我自己用的对照表左边是 n 的规模右边是这个规模下能通过的复杂度上限换算基准按 1e8 次简单操作每秒算。数据规模 n可接受的复杂度典型算法举例n ≤ 10O(n!) 或 O(2^n)全排列枚举、暴力搜索n ≤ 20O(2^n)状态压缩、子集枚举n ≤ 100O(n^3)三重循环、简单区间 DPn ≤ 1000O(n^2)二维 DP、朴素最短路n ≤ 1e5O(n log n)排序、二分、堆、树状数组n ≤ 1e6O(n) 且常数小线性扫描、前缀和、双指针n ≤ 1e7O(n) 且必须做 I/O 优化快读、逐字节处理用这张表的方式很直接题目说 n ≤ 1e5那就意味着 O(n^2) 的写法大约是 1e10 次操作必死不管你的代码写得多精简。这时候你要么换算法要么想清楚有没有 O(n log n) 或者 O(n) 的做法。我见过太多这样的情况题目是“给定一个长度为 n 的数组q 次询问区间和”n 和 q 都是 1e5有人写了个双层循环每组询问都从头加到尾。这个代码在样例上n6, q3跑得完美提交之后必然超时因为最坏情况是 1e5 × 1e5 1e10 次加法。标准解法是前缀和预处理 O(n)每次询问 O(1)总复杂度 O(n q)。这个转化过程没有任何技巧含量纯粹是“看范围选工具”。2.2 常数因子是被低估的第二道坎复杂度对了也可能超时这是新手最难接受的一点。O(n) 的代码跑 1e6 的数据有人跑 5 毫秒有人跑 400 毫秒差距全在常数上。什么会放大常数内存访问的局部性排在前面。二维数组按行访问和按列访问在 n2000 的时候能差出三到五倍的耗时因为按列访问会让 CPU 缓存反复失效。这不是玄学是硬件层面的事缓存行一次加载 64 字节你按行访问时这些数据马上都能用上按列访问时每次只能用到其中 4 个字节剩下的都被浪费了。函数调用也算。一个被调用 1e7 次的函数哪怕函数体只有一行调用开销本身就够呛。C 语言里做小函数建议加static inline让编译器有机会内联尤其在评测机开了优化的情况下效果明显。当然如果你本地编译没开优化加不加可能看不出差别但提交上去是有区别的。取模和除法比加减乘慢一个数量级。在需要大量取模的题里比如计数类问题能合并的取模就合并能用位运算代替的比如对 2 的幂取模就用位运算。这一条在 n 到 1e7 的时候才会体现出来n 小的时候不用管。还有读写内存的模式。频繁malloc和free是灾难vector不预留空间导致的反复扩容也是灾难——每次扩容都要把老数据全部复制一遍1e6 个元素如果扩容二十次复制的总量是千万级。养成习惯知道大概要放多少元素就先reserve一下。3. 输入输出最容易被忽视的时间黑洞3.1 scanf 与 cin 的真实差距纯 C 的scanf在绝大多数场景下是够用的1e5 级别的输入毫无压力1e6 级别也能扛。真正会出问题的是两个地方一是用 C 的cin而又没关同步二是在超大输入1e6 以上下还要用格式化输出。cin默认和 C 的 stdio 保持同步这个机制是为了让你能混用cin和scanf而不出错代价是每次读写都要过一遍同步检查。解决办法是在main开头加两行ios::sync_with_stdio(false); cin.tie(nullptr);加了之后cin的速度能追平甚至超过scanf。但有个坑必须记住关掉同步之后cin和scanf绝对不能混用混用的结果是输入顺序错乱表现出来就是“答案莫名其妙不对”而且极难排查因为代码逻辑看起来毫无问题。还有一个更隐蔽的endl。endl不只是输出一个换行符它还会强制刷新缓冲区。在循环里用cout x endl输出 1e5 个数每一次都触发一次系统调用级别的刷新慢得离谱。换成\n就没事了。这个坑我踩过一个只需要输出 1e5 行的题把endl换成\n之后从超时变成了 60 毫秒。3.2 手写快读与批量输出的写法当输入规模到 1e6 甚至 1e7scanf也开始吃力了这时候要上快读。原理很简单getchar逐字符读比scanf的格式解析快因为省掉了格式串的解析开销。#include stdio.h static inline int readInt(void) { int c getchar(), x 0, f 1; while (c ! EOF (c 0 || c 9)) { if (c -) f -1; c getchar(); } if (c EOF) return 0; while (c 0 c 9) { x x * 10 (c - 0); c getchar(); } return x * f; }这段代码有几个细节值得说。c声明成int而不是char因为getchar在文件结束时返回EOF通常是 -1char类型在某些平台上是有符号的比较时可能出问题。循环里的EOF判断不能省否则读到输入末尾会死循环表现出来还是超时但原因完全不同。负数处理用f标记避免对-2147483648取反溢出。输出端同理如果题目要输出 1e6 个数逐个printf也是有成本的。可以自己攒缓冲区static char obuf[1 20]; static int olen 0; static inline void writeInt(int x) { if (x 0) { obuf[olen] 0; return; } if (x 0) { obuf[olen] -; x -x; } char tmp[12]; int t 0; while (x) { tmp[t] (char)(0 x % 10); x / 10; } while (t) obuf[olen] tmp[--t]; }最后在main返回前fwrite(obuf, 1, olen, stdout);一次性刷出去。缓冲区大小设成 1 到 4 MB 都行注意别超过题目可能的内存限制。这套写法在 1e6 级别的输出上比printf快三到五倍实测过很多次。注意手写快读只在真的需要的时候用。1e5 以内的输入scanf完全够写快读反而增加出错概率。而且快读代码里如果漏了负号、漏了 EOF 判断调试成本很高。3.3 多组数据下的 I/O 细节多组测试数据的题有个固定套路读入通常写成while (scanf(%d, n) ! EOF) { /* 处理 */ }或者题目明确给了组数 T那就scanf(%d, T); while (T--) { ... }。这两种写法本身没问题问题出在“每组数据处理完要清理状态”这件事上。如果每组数据都要把一个大数组清零而 T 又很大这部分开销会累积。有个常见做法是用一个“访问标记数组”加时间戳代替每次都memsetint vis[N], stamp[N], cur 0; /* 每组数据开始时 */ cur; /* 判断是否访问过 */ if (stamp[u] ! cur) { stamp[u] cur; vis[u] 0; }这样每次“清空”的成本从 O(N) 降到 O(1)只在真正访问到某个位置时才初始化。这个技巧在 T 很大、N 也很大、但每组数据实际用到的元素很少的场景下效果极其明显。4. 算法与数据结构层面的典型陷阱4.1 循环里反复算同一个东西这是最普遍的超时原因之一而且极其隐蔽因为代码看起来“没错”。最经典的是strlen/* 慢每次循环都重新数一遍长度 */ for (int i 0; i strlen(s); i) { /* ... */ }strlen是 O(n) 的放在循环条件里就变成了 O(n^2)。字符串长度 1e5 的时候这就是 1e10 次字符扫描必死。改成先取长度int len strlen(s); for (int i 0; i len; i) { /* ... */ }类似的还有在循环里反复算pow(2, i)、反复算数组长度、反复调用一个返回常量的函数。这些东西编译器有时候能帮你优化掉有时候不能不要赌。还有一种变体是在双层循环里做不必要的重复计算。比如求两两之间的某种值内层循环里每次都重新算一遍a[i] * a[i]完全可以提到外层。这类优化的收益可能只有百分之二三十但在卡时间的边缘情况下就是生与死的区别。4.2 初始化开销memset 与容器的反复构造memset本身很快一个 1e6 的int数组清零也就一两毫秒。但如果你有 1e4 组测试数据每组都清零一个 1e6 的数组那就是 1e10 字节的写入妥妥超时。判断标准很简单算一下“清零总字节数”超过 1e8 就要警惕。解决办法有三种。一是缩小数组看能不能只清实际用到的部分。二是用上面说的时间戳技巧。三是把数组开在全局全局数组在程序启动时已经被清零一次如果题目只有一组数据连memset都不用写。容器这边的问题主要在vector和map。vector不预留空间会反复扩容扩容时要把已有元素全部复制到新内存1e6 个元素扩容约 20 次复制总量是 O(n) 的两倍左右虽然渐进复杂度没变但常数上去了。养成v.reserve(n)的习惯成本几乎为零。map是红黑树每次操作 O(log n) 且常数不小1e6 次插入可能要好几秒。如果键的范围可控比如都是 1 到 1e6 的整数直接用数组当哈希表速度能快一个数量级。unordered_map好一些但仍有哈希计算和链表遍历的开销而且某些实现下会被特殊数据卡成 O(n)。4.3 递归、容器与常数选择递归写起来清爽但每一层调用都有栈帧开销。深度到 1e5 的时候光是函数调用本身就可能吃掉几百毫秒而且还有栈溢出的风险默认栈空间通常只有几 MB。能改成迭代的尽量改尤其是线性递归。举个具体的求斐波那契数列第 n 项n 到 1e6。用朴素递归是 O(2^n)直接爆炸用带记忆化的递归是 O(n) 但每层一次函数调用用两个变量迭代是 O(n) 且没有调用开销。三者渐进复杂度后两个一样实测差距在三到五倍。再比如并查集。不写路径压缩的话最坏情况退化成链单次查询 O(n)整体 O(n^2)。加上路径压缩和按秩合并之后接近 O(1)。这个优化只多写三行代码收益巨大属于必做项。还有排序。需要排序的时候优先用标准库的qsort或者 C 的sort不要自己手写冒泡或者选择排序。手写快排如果基准点选得不好比如固定选第一个元素遇到有序数据会退化成 O(n^2)而标准库的排序实现通常做了三数取中和小区间插入排序的优化能扛住各种刁钻数据。场景常见慢写法快写法量级差距循环里求长度for(i0;istrlen(s);i)先存lenO(n^2) → O(n)频繁插入vector不reserve先reserve(n)常数 1.5~2 倍键为小整数mapint,int直接用数组数倍到十数倍线性递归递归求第 n 项两个变量迭代3~5 倍并查集不压缩路径压缩 按秩合并O(n) → 近似 O(1)5. 一次完整的改造实录从 TLE 到 AC5.1 题目与暴力解法我拿一道很常见的题型做演示给定 n 个整数接下来 q 次询问每次给出 l 和 r输出下标从 l 到 r 的元素之和。数据范围是 n, q ≤ 100000元素绝对值不超过 1e4多组测试数据。先看暴力版本这也是绝大多数人第一反应写出来的东西#include stdio.h int a[100005]; int main(void) { int n, q; while (scanf(%d%d, n, q) ! EOF) { for (int i 1; i n; i) scanf(%d, a[i]); while (q--) { int l, r; scanf(%d%d, l, r); long long sum 0; for (int i l; i r; i) sum a[i]; printf(%lld\n, sum); } } return 0; }逻辑完全正确样例也能过。但是最坏情况——每次询问都是l1, rn——内层循环跑满 n 次总共 q × n 1e10 次加法。按每秒 1e8 到 3e8 次算需要三十秒到一百秒评测机那边直接判超时连商量的余地都没有。这里我要强调一个心态问题看到超时不要第一反应去“优化代码”比如把printf换成putchar、把int换成register。这些改动顶多省 10%而你需要省 99%。方向错了再努力也没用。5.2 定位瓶颈定位的方法很朴素算最坏情况下的内层操作次数。这道题的内层就是那个求和循环循环次数是r - l 1最坏 n。外层是 q 次询问所以是 n × q。把数据范围的数字代进去1e5 × 1e5 1e10超过预算两个数量级。下一步是问自己这 1e10 次计算里有多少是重复的答案是绝大部分。从 1 加到 100000 和从 1 加到 99999前者的结果只比后者多最后一项。但暴力写法每次都从头加把前面的工作全部重做了。这就是典型的“重复计算”型瓶颈。找到了重复优化方向就明确了把重复的部分缓存起来。前缀和就是干这个的。定义pre[i] a[1] a[2] ... a[i]那么区间和就是pre[r] - pre[l-1]一次减法搞定。预处理 O(n)每次询问 O(1)。5.3 改造后的版本与实测对比#include stdio.h static int a[100005]; static long long pre[100005]; int main(void) { int n, q; while (scanf(%d%d, n, q) ! EOF) { pre[0] 0; for (int i 1; i n; i) { scanf(%d, a[i]); pre[i] pre[i - 1] a[i]; } while (q--) { int l, r; scanf(%d%d, l, r); printf(%lld\n, pre[r] - pre[l - 1]); } } return 0; }改动只有三处多了一个pre数组、读入时顺手累加、询问时改成减法。总操作次数从 1e10 降到 1e5 1e5 2e5快了五个数量级。在我的机器上nq1e5 的单组数据暴力版本跑不完几十秒前缀和版本连读入带计算不到 20 毫秒。这里有个容易忽略的细节pre数组用了long long。因为 n 最大 1e5每个元素绝对值 1e4总和最大是 1e9这个数用int其实装得下int上限约 2.1e9但很接近了。如果题目把元素范围改成 1e9那总和会达到 1e14必须用long long。这类溢出问题在 OJ 上表现为“答案错误”而不是超时但根源是同一种思维习惯——动手前先把数值范围算一遍。再看一个和 I/O 相关的改造。假设有一道题要输出 1e6 行每行一个整数用printf(%d\n, x)循环输出。我实测过这一百万次调用大约耗时 180 到 250 毫秒取决于机器。改成上面说的缓冲区写法之后降到 40 毫秒左右。如果题目限时 1000ms 且算法本身已经吃掉 700ms这 150 毫秒的差距就是过与不过的分界线。改造项改造前耗时改造后耗时提升幅度区间求和1e5 次询问超时无法完成约 20 ms五个数量级输出 1e6 个整数约 200 ms约 40 ms约 5 倍读入 1e6 个整数scanf约 150 ms—基准读入 1e6 个整数快读—约 50 ms约 3 倍endl改\n1e5 行超时约 60 ms从不可用到可用6. 排查清单与常见问题速查6.1 提交前自查流程我现在每次提交前会过一遍下面这个流程平均花两分钟比提交之后等结果、看红字、改代码、再提交要快得多。第一步把题目描述里的数据范围抄在手边算出 n 的最大值对应可接受的复杂度和自己写的算法对一下。这一步能拦下八成必然超时的代码。第二步找最内层循环数它最多执行多少次。把 n 的最大值代进去得到总操作数除以 1e8估算秒数。超过限时的三分之一就要动手优化。第三步检查循环里有没有重复计算的东西尤其是循环条件里的函数调用以及内层循环里和外层无关的表达式。第四步检查初始化开销。多组数据的题算一下“每次清零的字节数 × 组数”超过 1e8 就要想办法。第五步检查输入输出。输入超过 1e6 或者输出格式是逐行的大量数据考虑快读和缓冲输出。第六步检查有没有可能死循环。while条件里变量的更新语句漏写、EOF判断缺失、浮点数比较用等号这些都是常客表现同样是超时。提示如果你怀疑某个循环体拖了后腿可以把它先注释掉换成固定值看运行时间的变化。这种“二分定位”的办法在几万行的代码里很有用。6.2 常见问题对照表现象最可能的原因处理方式小样例过大样例超时复杂度不够算法方向错换算法看是否能预处理或复用中间结果所有测试点都超时连小数据也是死循环或读入卡住检查while的更新、EOF判断、多组数据读入格式偶尔超时偶尔通过常数在临界点机器负载波动砍常数把操作数压到限时的三分之一以下单组数据正常多组就超时初始化开销过大用时间戳数组或缩小初始化范围改成 C 写法后更慢没关iostream同步或用了endl关同步endl换成\n输出量很大时超时逐次输出触发刷新攒缓冲区批量输出递归题超时且伴随异常退出递归过深或重复子问题改迭代或加记忆化6.3 几条用血换来的小经验第一条编译优化选项在本地和评测机可能不一样所以不要在本地测出“刚好卡线”就开始庆幸。我现在的习惯是把本地的数据规模放大到题目给定的最大值甚至再乘个两倍如果本地在这个规模下仍然只用了限时的十分之一我才敢放心提交。第二条int溢出有时候表现得像超时。比如你在一个循环里做累加溢出成负数之后导致循环条件永远成立那就是彻底的死循环。这种情况特别难查因为你看代码看不出问题要盯数值。所以涉及累加、乘法的变量先算一下理论上限。第三条测试数据的边界往往是最毒的。n 取最大值、所有元素都相同、所有询问都是同一个区间这些情况在随机数据里出现概率极低但出题人一定会放进去。所以本地测试不要只用随机生成器要手动构造这几个极端情况。第四条超时和内存超限有时候会互相转化。你为了省时间开了个巨大的数组做打表结果内存超了你把数组改小改用map结果时间又不够了。这时候要找平衡点通常的做法是把范围最大的那一维压到刚好够用不要预留太多。第五条也是我觉得最有用的一条如果你已经改了三轮还是超时停下来把算法重新想一遍而不是继续抠代码。抠常数能救回来的时间最多两三倍而换算法能带来数量级的差别。我自己的经验是第一次超时先检查常量和 I/O如果还不过直接推翻重写比在旧代码上打补丁快得多。有一次我做一道统计类题目n 是 2e5我先写了个 O(n^2) 的比较超时改成排序后二分还是超时最后发现题目要求的是“不同元素的个数”用一次线性扫描加标记数组就完事了复杂度降到 O(n)。整个过程我花了四十分钟在错误的算法上打转而正确答案只需要思考三分钟。这件事之后我就养成了习惯写代码前先在纸上写清楚复杂度和最内层操作次数哪怕只是一行字。