提交按钮点下去红色的 Time Limit Exceeded 弹出来这行字对刷过题的人都不陌生。它不像编译错误那样直接指出哪一行有语法问题也不像答案错误那样至少说明程序跑完了它就是一句冷冰冰的“超出时间限制”——你的逻辑可能完全正确只是判题机没耐心等你。在 C 语言的 OJ 系统里超时是最常见、也最容易被误判为“玄学”的一类问题有人把同一份代码从 C 换成 C 就过了有人加了一行ios::sync_with_stdio(false)就从 TLE 变成 AC还有人死活想不通自己明明写的是“正解”为什么还是被卡。我这些年帮人看代码、自己踩坑见过太多把时间浪费在“再交一次试试”上的情况。这篇内容就是围绕“C 语言 OJ 系统超时”这件事把原因拆开、把定位方法讲透、把能直接抄的优化手段列清楚。适合刚接触在线评测、被 TLE 反复折磨的新手也适合想把自己代码常数压下去的中阶选手。读完之后你至少能做到看到超时不再盲目重交而是能判断它到底是算法选错了、常数太大了还是压根没读对数据。1. 先把“超时”这件事拆开看1.1 判题机的那一秒到底有多长很多人对“1 秒”没有概念以为 1 秒很长。实际上在线评测平台给出的Time Limit: 1000 MS指的是你的程序从开始运行到结束整个进程占用 CPU 的时间不能超过 1 秒。而这 1 秒里还要扣掉程序启动、动态库加载、输入输出缓冲刷新的开销真正留给你计算的余量往往只有 0.8 秒左右。更关键的是不同平台的机器性能差别很大同一份代码在 A 平台跑 300ms在 B 平台可能就跑 900ms这不是玄学是 CPU 主频、编译器版本、优化选项、甚至内存带宽的共同结果。那 1 秒能跑多少次运算业内比较通用的保守估算是每秒 10^8 次左右的简单整数运算。注意这里说的是“简单整数运算”一次加减、一次比较、一次数组下标寻址大概算 1 次而一次整数除法、一次取模、一次浮点乘除代价可能是前者的几倍到几十倍一次内存随机访问如果缓存不命中代价可能是上百个时钟周期。所以你不能简单地把循环次数乘以循环体行数当运算量得看循环体里干了什么。我通常会用一个粗略公式先给自己吃颗定心丸可接受运算量 ≈ 时间限制(秒) × 10^8 实际运算量 ≈ 最内层循环执行次数 × 单次迭代的平均代价系数如果算出来实际运算量比可接受量高一个数量级那基本不用挣扎了改算法如果只高出两三倍那大概率是常数问题压一压还有救。这个判断非常重要因为它直接决定你接下来是去翻算法书还是去翻优化技巧。1.2 超时、答案错误、运行错误别混为一谈我见过太多人把“运行错误”当成“超时”来优化。这两种情况的处理方向完全相反超时是“跑太慢”运行错误是“跑崩了”。你把一个因为数组越界导致段错误的程序拿去优化常数优化到天荒地老也过不了。判题结果一般这么分结果缩写全称真实含义常见原因ACAccepted通过无TLETime Limit Exceeded超时复杂度过高、常数过大、死循环MLEMemory Limit Exceeded内存超限数组开太大、递归太深、容器疯狂扩容RERuntime Error运行错误数组越界、除零、栈溢出、非法指针WAWrong Answer答案错误逻辑错、边界漏、溢出PEPresentation Error格式错误多空格、少换行CECompile Error编译错误语法、头文件、编译器差异这里有个很容易被忽略的点死循环通常表现为 TLE 而不是卡死。判题机有超时保护你的while(1)会在时间到的时候被杀掉返回 TLE。所以看到一个“必超时”的题目先别急着骂数据检查一下循环变量有没有更新、边界条件是不是写反了、scanf的返回值有没有处理。我就遇到过一次读多组数据时写了while (scanf(%d, n))当输入结束scanf返回 0循环不退出直接死循环 TLE。正确写法是while (scanf(%d, n) ! EOF)或者while (scanf(%d, n) 1)。还有一种情况是栈溢出被误认为超时。有些平台的栈溢出会直接返回 RE但也有平台在崩溃前反复尝试、表现成 TLE。如果你在函数里定义了int a[1000000]这种局部大数组几乎必崩因为默认栈空间通常只有几 MB。解决办法很简单把大数组挪到全局全局变量在静态存储区空间大得多而且默认初始化为 0。提示看到 TLE 的第一件事不是改代码是先把题目描述里的数据范围抄下来。数据范围决定了你能用什么复杂度这是所有判断的起点。1.3 三步定位法先估算再计时最后删减我处理超时的固定流程就三步很少走弯路。第一步估算复杂度。看数据范围n ≤ 1000的话 O(n²) 就是 10^6随便过n ≤ 10^5的话 O(n²) 是 10^10必挂得想 O(n log n)n ≤ 10^6的话连 O(n log n) 都要小心尽量往 O(n) 靠。这一步不用写代码纯算术三十秒就能得出结论。第二步本地计时。别靠感觉直接上clock()。在main开始和结束各打一个点中间输出耗时#include stdio.h #include time.h int main(void) { clock_t st clock(); /* 你的核心逻辑 */ clock_t ed clock(); fprintf(stderr, time used: %.3f s\n, (double)(ed - st) / CLOCKS_PER_SEC); return 0; }注意输出到stderr这样不会混进标准输出影响答案比对。本地跑出来的时间乘以 1.5 到 2大致就是判题机上的时间因为本地机器通常更新更快而且判题机往往有沙箱开销。第三步逐段删减。如果本地就超了那就用二分法先注释掉后半段看时间掉多少再注释前半段。哪一段是耗时大头一目了然。这比盯着代码发呆高效得多。我曾经帮人看一道题他坚称自己是 O(n)结果一计时发现 90% 时间耗在一个他自己都忘了的memset上——每轮循环清空一个 10^7 的数组循环 10^5 次那能不超时吗。2. 复杂度选错九成超时都死在这里2.1 一张表看懂数据范围和复杂度的对应关系这张表我建议每个刚开始刷题的人都存一份看题先看范围范围决定复杂度复杂度决定你能不能写。数据规模 n能承受的复杂度典型算法危险区n ≤ 10O(n!)全排列暴力无n ≤ 20O(2^n)状态压缩、子集枚举n 到 25 就悬n ≤ 100O(n³)Floyd、三重循环 DPn 到 500 必挂n ≤ 1000O(n²)普通 DP、双重循环n 到 5000 危险n ≤ 10^5O(n log n)排序、二分、线段树、堆O(n²) 绝对不行n ≤ 10^6O(n) 或 O(n log n) 偏紧线性扫描、前缀和常数大就挂n ≤ 10^8O(n) 且常数极小简单累加基本只存在于理论举个具体例子。一道题给n ≤ 10^5让你统计数组里有多少对(i, j)满足a[i] a[j]且i j也就是逆序对。很多人第一反应是双重循环long long cnt 0; for (int i 0; i n; i) for (int j i 1; j n; j) if (a[i] a[j]) cnt;这段代码逻辑完全正确但 n 10^5 时内层总共要跑约 5×10^9 次比较1 秒的判题机跑 10^8 次都费劲差了整整五十倍交上去必定 TLE。这时候不是优化常数能救的得换算法归并排序求逆序对或者树状数组离散化复杂度降到 O(n log n)n 10^5 时大约 1.7×10^6 次操作稳得很。我给个能直接用的归并版本long long ans 0; int tmp[MAXN]; void merge_sort(int l, int r) { if (l r) return; int mid l (r - l) / 2; merge_sort(l, mid); merge_sort(mid 1, r); int i l, j mid 1, k l; while (i mid j r) { if (a[i] a[j]) tmp[k] a[i]; else { ans mid - i 1; tmp[k] a[j]; } } while (i mid) tmp[k] a[i]; while (j r) tmp[k] a[j]; for (int p l; p r; p) a[p] tmp[p]; }这里mid - i 1是关键当右边元素小于左边元素时左边从 i 到 mid 的所有元素都和它构成逆序对。这个计数方式比循环里加一堆判断要快得多因为它是“批量结算”。2.2 嵌套循环里的重复计算最要命有些代码复杂度看着没问题但循环体里藏了重复劳动。最典型的三种第一种循环条件里反复调用函数。比如for (int i 0; i strlen(s); i)。strlen是 O(n) 的放在循环条件里整个循环就变成 O(n²)。n 10^5 的字符串直接超时。正确做法是先算出来存着int len strlen(s); for (int i 0; i len; i) { /* ... */ }注意 C 的std::string::size()是 O(1) 的不存在这个问题但 C 的strlen是实打实要扫到\0的。这个坑每年都能坑一大批人。第二种循环体内重复做同样的计算。比如for (int i 0; i n; i) { for (int j 0; j n; j) { sum a[i] * b[j] a[i] * c[j]; } }a[i]在内层循环里被取了两次虽然现代编译器多半会把它提到寄存器但在没有开优化或者编译器比较保守的情况下这就是白白多出来的内存访问。养成习惯能提的常量提到外层for (int i 0; i n; i) { int ai a[i]; for (int j 0; j n; j) sum ai * (b[j] c[j]); }第三种循环里调sqrt、pow、取模。这几个都是慢操作。sqrt一次大概几十个时钟周期放在 10^7 次的循环里就是灾难。如果只需要判断完全平方数用整数开方或者预处理表如果取模次数太多考虑先累加再统一取模只要保证中间不溢出就行。2.3 容器和数据结构选错等于自带减速带C 语言里选择没那么多但 C 写 OJ 的人越来越多这里面的坑也多。std::map每次插入、查找都是 O(log n)而且常数很大因为它是红黑树节点分散在堆上缓存极不友好。n 10^5 次操作map可能要跑几百毫秒换成排序加二分或者直接用数组下标做桶时间能掉一个数量级。unordered_map理论上是 O(1)但它有哈希冲突出题人如果存心卡构造一组冲突数据就能让退化到 O(n)所以关键题目上我一般不敢完全依赖它。std::vector的push_back在容量不足时会重新分配并整体拷贝虽然摊还复杂度是 O(1)但如果你预先知道大小一定要reservevectorint v; v.reserve(n); for (int i 0; i n; i) v.push_back(x);这一行reserve能省掉十几次重新分配和元素搬移在 n 10^6 的时候差别非常明显。还有一个隐蔽的坑二维数组的访问顺序。C 语言是行优先存储a[i][j]里 j 连续变化时是顺序访问内存缓存命中率高如果你写成a[j][i]每次跳一整行缓存基本全废同样的循环次数可能慢三到五倍。这个不是算法问题是硬件问题但对 TLE 的影响很实在。2.4 递归不是不能用但要看清楚代价递归写起来舒服代价是函数调用开销和栈空间。一次函数调用大概几十个时钟周期深度 10^5 的递归光调用开销就是几百万周期再加上每层压栈出栈很容易超时。更麻烦的是递归深度超过栈空间会直接崩。如果递归本身是指数级的比如朴素斐波那契int fib(int n) { if (n 1) return n; return fib(n - 1) fib(n - 2); }n 40 就要跑上亿次n 50 直接跑不完。这种必须加记忆化把算过的结果存数组long long memo[100]; int vis[100]; long long fib(int n) { if (n 1) return n; if (vis[n]) return memo[n]; vis[n] 1; return memo[n] fib(n - 1) fib(n - 2); }加上这两行复杂度从 O(2^n) 掉到 O(n)n 90 都是瞬间出结果。很多人以为自己是“递归超时”其实是“重复子问题没处理”本质还是复杂度问题。3. 算法对了还被卡常数优化的实战清单3.1 输入输出可能是你没算到的开销有些题目输入量极大比如 10^6 个整数甚至更多。这时候 I/O 的占比可能超过计算本身。cin和cout默认和 C 的stdio同步速度比scanf慢不少关掉同步能快好几倍ios::sync_with_stdio(false); cin.tie(nullptr);但注意关掉同步之后就不能混用cin和scanf了否则读入顺序会乱。另外endl会强制刷新缓冲区在循环里用endl输出 10^5 行那个刷新开销足够让你 TLE一律换成\n。如果连scanf都嫌慢可以上手写快读。原理是getchar逐字符读避开格式化解析的开销inline int read() { int x 0, f 1; int c getchar(); while (c 0 || c 9) { if (c -) f -1; c getchar(); } while (c 0 c 9) { x x * 10 (c - 0); c getchar(); } return x * f; }这里有个细节必须强调c要用int而不是char。因为getchar()返回的是intEOF 是 -1如果你用char接某些平台上char是无符号的EOF 会被截断成 255导致判断失效最后变成死循环 TLE。这个坑非常经典。输出同理如果输出量巨大可以用putchar手写输出或者攒到缓冲区一次性输出。不过大部分题目用printf就够了别过早优化先确认瓶颈在不在 I/O。3.2 多组数据下的清空操作是隐形杀手带多组数据的题目很多人习惯在每组数据开头来一发memset(a, 0, sizeof(a))。如果数组只有几千个元素无所谓如果数组是 10^7 的int一次就是 40MB 的内存写入而组数可能有 10^5 组总写入量 4TB别说 1 秒1 分钟都跑不完。正确思路是只清用到的那部分for (int i 0; i n; i) a[i] 0;n 是当前这组数据的实际规模通常远小于数组上限。这一改时间可能从 TLE 直接掉到几十毫秒。还有一种情况是用“时间戳”代替清空。比如标记数组vis[]与其每次全清不如开一个stamp[]记录每个位置最后一次被标记的组号判断时比较组号是否一致即可。这个技巧在并查集、图论题里非常常用属于老选手的基本功。提示看到题目里有T组数据且数组开得很大先把所有memset找出来这是超时的高发区。3.3 一份能照着改的常数优化清单下面这些手段不影响正确性纯粹是让同样的逻辑跑得更快。按性价比排序优化手段典型收益适用场景注意事项局部变量替全局变量中热点循环全局变量访问要走地址提常量到循环外中内层重复取值编译器不保证总能优化数组按行访问大二维 DP、矩阵缓存局部性reserve预分配中vector 大量 push_back只在知道大小时有效用\n替endl大大量输出endl 每次刷新手写快读大输入量 10^6 以上注意 EOF 判断用 int减少取模次数中循环内累加防溢出用位运算替乘除 2小极端卡常编译器多数已优化循环展开小极热点可读性下降明显预计算打表大多次查询固定值一次性开销转常数关于位运算我要泼一点冷水i * 2和i 1在现代编译器开 O2 的情况下生成的机器码通常一样指望这个救命不现实。真正有用的是减少内存访问和减少函数调用这两块才是常数的大头。还有一个常被忽略的点取模运算很慢。整数除法在 x86 上大概要 20 到 40 个时钟周期比加法慢一个数量级。如果循环里每次都% MOD累积起来很可观。可以改成累加到一个较大的阈值再取模或者用减法代替取模当模数固定且数值范围可控时。3.4 语言和编译选项的差异比你想的大同一份逻辑用 C 编译和用 C 编译跑出来的时间可能差 20% 到 50%。一般来说 C 的标准库更轻启动开销小纯计算题上略占优势但如果你的代码用了大量 C 容器那当然还是选 C。提交时看清楚平台的选项能选C (gcc)就别犹豫。本地测试时记得开和判题机接近的优化等级。很多人本地用默认的-O0测程序跑 3 秒吓得去改算法实际上判题机用-O2跑起来只有 400ms。反过来本地开-O2测得很美判题机没开优化照样 TLE。这个信息一般在平台的帮助页面能查到花两分钟看一眼能省掉大量误判。gcc -O2 -stdc11 -o prog prog.c另外编译选项里的-static、栈大小设置这些一般平台是固定的你改不了但知道它们存在有助于理解为什么同一份代码在不同平台表现不同。4. 几个真实改造过程的复盘4.1 案例一从双重循环到树状数组有个同学拿来一段代码题目是统计区间内小于等于某值的元素个数n 10^5查询 q 10^5。他写的是每次查询扫一遍区间for (int i 0; i q; i) { int cnt 0; for (int j l[i]; j r[i]; j) if (a[j] x[i]) cnt; printf(%d\n, cnt); }复杂度 O(nq) 10^10必挂。改造成离线处理加树状数组把所有查询按 x 排序把数组元素也按值排序逐个把小于等于当前 x 的元素插进树状数组然后区间查询就是两次前缀和相减。复杂度 O((nq) log n)10^5 规模下大约 3×10^6 次操作跑 100ms 出头。这个改造的关键不是树状数组本身而是把“每次重新扫”变成“增量维护”。很多超时题的破局点都在这里你有没有办法把重复计算的部分缓存下来。4.2 案例二字符串拼接的隐藏二次方另一个典型是字符串处理。有人这么写char s[100005] ; for (int i 0; i n; i) { char t[2] {c[i], \0}; strcat(s, t); }看起来每次只追加一个字符但strcat每次都要从s的开头扫到结尾找\0第 i 次追加要扫 i 个字符总共 O(n²)。n 10^5 时是 5×10^9 次字符访问稳稳超时。改法很简单维护一个长度指针int len 0; for (int i 0; i n; i) s[len] c[i]; s[len] \0;同样的效果O(n)。C 里对应的是不要在循环里写s s ch用s.push_back(ch)或者先reserve再追加。4.3 案例三图论题用邻接矩阵的代价一道 n 10^5、m 2×10^5 的图论题有人开了int g[100005][100005]。先不说时间这个数组本身就要 40GB 内存编译都过不了。就算把 n 缩小到 5000矩阵是 25×10^6 个 int100MB也超内存了。正确做法是邻接表。C 语言用数组模拟int head[MAXN], nxt[MAXM], to[MAXM], ecnt 0; void add_edge(int u, int v) { to[ecnt] v; nxt[ecnt] head[u]; head[u] ecnt; }遍历时顺着head[u]一路走nxt。这个写法比vectorint g[MAXN]更快因为内存连续、没有动态分配开销而且缓存友好。在 10^5 级别的图上这个差别能到两倍以上。4.4 案例四一份被 memset 拖死的代码最后这个案例特别有代表性。代码逻辑是标准的 BFSn 10^5m 2×10^5理论上完全跑得动。但他每组数据开头都有memset(vis, 0, sizeof(vis)); memset(dis, 0, sizeof(dis)); memset(head, -1, sizeof(head));三个数组加起来大概 2MB 多单次清空不到 1ms看起来不多。但题目有 10^4 组数据总计就是 20GB 的内存写入20 秒起步。改法vis用时间戳dis只清1..nhead只清1..n。改完之后总时间从 20 秒掉到 200ms。这个案例我印象特别深因为它说明超时不一定出在循环里也可能出在循环外面的初始化而初始化往往最容易被忽略因为大家潜意识里觉得“清个数组能有多慢”。5. 超时排查速查表与踩坑经验5.1 一张表覆盖八成超时场景现象最可能的原因快速验证方法解决方向小数据能过大数据 TLE复杂度过高按数据范围估算运算量换算法所有数据都 TLE包括样例死循环本地跑样例看是否卡住查循环变量、EOF 判断本地快提交慢编译优化差异、机器差异本地开 -O2 重测换语言、压常数多组数据越跑越慢初始化范围过大注释掉 memset 再测只清有效部分输入特别大时 TLEI/O 瓶颈换 scanf / 快读对比优化输入递归题 TLE重复子问题、深度过大加计数器统计调用次数记忆化或改迭代图论题 TLE 或 MLE邻接矩阵看数组大小改邻接表字符串题 TLE反复 strlen、strcat检查循环条件缓存长度、指针追加排序后 TLE用了低效排序换 std::sort 对比用库函数随机数据能过特定数据 TLE哈希冲突、退化换数据结构避开 unordered_map5.2 那些“不是超时却被判超时”的坑有几个情况特别冤明明代码没问题就是过不了。第一输出格式导致的超时。有些平台的比对程序在遇到格式不符时会反复重试读取表现成超时。比如题目要求每行末尾不能有空格你多打了一个空格可能不是 PE 而是 TLE。这类问题只能靠仔细看输出要求或者用diff本地比对。第二文件读写没关。极少数题目要求从文件读写如果你开了文件流但没关闭缓冲区不刷新程序结束时可能卡在刷新上。虽然少见但遇到了很难查。第三while循环里的scanf返回值没判断。前面提过while (scanf(%d, n))在输入结束后返回 0循环不退出直接死循环。正确写法是判断! EOF或者 1。这个错误的隐蔽性在于样例输入正常结束程序就跑完了看起来没问题但判题机可能有多组测试文件或者输入末尾没有额外换行就卡住了。第四随机数种子用了时间。极少数题目需要随机化算法如果种子用time(NULL)在某些沙箱环境里时间不变导致每次跑出一样的结果陷入退化路径表现成超时。这种情况改成固定种子反而更稳。第五递归深度刚好卡在边界。深度 10^5 的递归在某些平台栈空间够在某些平台不够表现可能是 RE 也可能是 TLE。稳妥起见深搜超过 10^5 层就考虑改迭代或者手动开栈。5.3 我自己的几条保命习惯最后分享几条我常年刷题养成的习惯都是被坑出来的。看题先看数据范围再看时间限制最后看内存限制。这三个数字决定了这道题的解法上限比题目描述本身还重要。数据范围 10^5 就是告诉你“别写 O(n²)”时间限制 1000ms 就是告诉你“常数别太浪”。写完先本地造极限数据。别用样例自测样例通常是最弱的。自己写个小脚本生成 n 10^5 的随机数据跑一遍计时心里就有数了。生成数据用 Python 或者 shell 都行几行代码的事python3 -c import random n 100000 print(n) print( .join(str(random.randint(1, 10**9)) for _ in range(n))) big_input.txt提交前把调试输出全删干净。有人留着printf在循环里输出到标准输出一方面拖慢速度另一方面污染答案。调试信息一律走stderr这是底线。不要迷信“再交一次”。判题机的负载确实会波动同一份代码可能这次 TLE 下次 AC但这只对临界情况成立。如果你的代码超时 3 倍以上重交一百次也没用。判断标准很简单本地开 O2 跑如果比时间限制高出很多就别浪费提交次数了。遇到玄学先怀疑自己。我见过太多人抱怨“平台卡我”最后一查是自己数组越界写坏了内存、或者循环边界差一。判题机是死的它不会针对你。真觉得数据有问题先把代码贴出来让人看大部分时候问题一眼就能被发现。保持一份自己的模板。快读、快写、常用宏、常用数据结构整理成一个文件每次开题直接复制。这不能解决算法问题但能让你少在重复劳动上犯错也少在 I/O 上浪费时间。模板这东西越用越顺手改着改着就变成自己的了。上面这些内容涵盖了从判断超时性质、估算复杂度、定位瓶颈、到具体优化手段的完整链条。真正上手的时候你会发现大部分 TLE 其实在第一步就能定性数据范围一摆出来该不该换算法就清楚了。剩下的常数优化属于锦上添花能压则压但别指望它救一个复杂度错误的方案。 
长河君 · 2026/11/3 8:53:53 · 阅读 1.2k C语言OJ超时排查：从复杂度到常数优化实战
提交按钮点下去红色的 Time Limit Exceeded 弹出来这行字对刷过题的人都不陌生。它不像编译错误那样直接指出哪一行有语法问题也不像答案错误那样至少说明程序跑完了它就是一句冷冰冰的“超出时间限制”——你的逻辑可能完全正确只是判题机没耐心等你。在 C 语言的 OJ 系统里超时是最常见、也最容易被误判为“玄学”的一类问题有人把同一份代码从 C 换成 C 就过了有人加了一行ios::sync_with_stdio(false)就从 TLE 变成 AC还有人死活想不通自己明明写的是“正解”为什么还是被卡。我这些年帮人看代码、自己踩坑见过太多把时间浪费在“再交一次试试”上的情况。这篇内容就是围绕“C 语言 OJ 系统超时”这件事把原因拆开、把定位方法讲透、把能直接抄的优化手段列清楚。适合刚接触在线评测、被 TLE 反复折磨的新手也适合想把自己代码常数压下去的中阶选手。读完之后你至少能做到看到超时不再盲目重交而是能判断它到底是算法选错了、常数太大了还是压根没读对数据。1. 先把“超时”这件事拆开看1.1 判题机的那一秒到底有多长很多人对“1 秒”没有概念以为 1 秒很长。实际上在线评测平台给出的Time Limit: 1000 MS指的是你的程序从开始运行到结束整个进程占用 CPU 的时间不能超过 1 秒。而这 1 秒里还要扣掉程序启动、动态库加载、输入输出缓冲刷新的开销真正留给你计算的余量往往只有 0.8 秒左右。更关键的是不同平台的机器性能差别很大同一份代码在 A 平台跑 300ms在 B 平台可能就跑 900ms这不是玄学是 CPU 主频、编译器版本、优化选项、甚至内存带宽的共同结果。那 1 秒能跑多少次运算业内比较通用的保守估算是每秒 10^8 次左右的简单整数运算。注意这里说的是“简单整数运算”一次加减、一次比较、一次数组下标寻址大概算 1 次而一次整数除法、一次取模、一次浮点乘除代价可能是前者的几倍到几十倍一次内存随机访问如果缓存不命中代价可能是上百个时钟周期。所以你不能简单地把循环次数乘以循环体行数当运算量得看循环体里干了什么。我通常会用一个粗略公式先给自己吃颗定心丸可接受运算量 ≈ 时间限制(秒) × 10^8 实际运算量 ≈ 最内层循环执行次数 × 单次迭代的平均代价系数如果算出来实际运算量比可接受量高一个数量级那基本不用挣扎了改算法如果只高出两三倍那大概率是常数问题压一压还有救。这个判断非常重要因为它直接决定你接下来是去翻算法书还是去翻优化技巧。1.2 超时、答案错误、运行错误别混为一谈我见过太多人把“运行错误”当成“超时”来优化。这两种情况的处理方向完全相反超时是“跑太慢”运行错误是“跑崩了”。你把一个因为数组越界导致段错误的程序拿去优化常数优化到天荒地老也过不了。判题结果一般这么分结果缩写全称真实含义常见原因ACAccepted通过无TLETime Limit Exceeded超时复杂度过高、常数过大、死循环MLEMemory Limit Exceeded内存超限数组开太大、递归太深、容器疯狂扩容RERuntime Error运行错误数组越界、除零、栈溢出、非法指针WAWrong Answer答案错误逻辑错、边界漏、溢出PEPresentation Error格式错误多空格、少换行CECompile Error编译错误语法、头文件、编译器差异这里有个很容易被忽略的点死循环通常表现为 TLE 而不是卡死。判题机有超时保护你的while(1)会在时间到的时候被杀掉返回 TLE。所以看到一个“必超时”的题目先别急着骂数据检查一下循环变量有没有更新、边界条件是不是写反了、scanf的返回值有没有处理。我就遇到过一次读多组数据时写了while (scanf(%d, n))当输入结束scanf返回 0循环不退出直接死循环 TLE。正确写法是while (scanf(%d, n) ! EOF)或者while (scanf(%d, n) 1)。还有一种情况是栈溢出被误认为超时。有些平台的栈溢出会直接返回 RE但也有平台在崩溃前反复尝试、表现成 TLE。如果你在函数里定义了int a[1000000]这种局部大数组几乎必崩因为默认栈空间通常只有几 MB。解决办法很简单把大数组挪到全局全局变量在静态存储区空间大得多而且默认初始化为 0。提示看到 TLE 的第一件事不是改代码是先把题目描述里的数据范围抄下来。数据范围决定了你能用什么复杂度这是所有判断的起点。1.3 三步定位法先估算再计时最后删减我处理超时的固定流程就三步很少走弯路。第一步估算复杂度。看数据范围n ≤ 1000的话 O(n²) 就是 10^6随便过n ≤ 10^5的话 O(n²) 是 10^10必挂得想 O(n log n)n ≤ 10^6的话连 O(n log n) 都要小心尽量往 O(n) 靠。这一步不用写代码纯算术三十秒就能得出结论。第二步本地计时。别靠感觉直接上clock()。在main开始和结束各打一个点中间输出耗时#include stdio.h #include time.h int main(void) { clock_t st clock(); /* 你的核心逻辑 */ clock_t ed clock(); fprintf(stderr, time used: %.3f s\n, (double)(ed - st) / CLOCKS_PER_SEC); return 0; }注意输出到stderr这样不会混进标准输出影响答案比对。本地跑出来的时间乘以 1.5 到 2大致就是判题机上的时间因为本地机器通常更新更快而且判题机往往有沙箱开销。第三步逐段删减。如果本地就超了那就用二分法先注释掉后半段看时间掉多少再注释前半段。哪一段是耗时大头一目了然。这比盯着代码发呆高效得多。我曾经帮人看一道题他坚称自己是 O(n)结果一计时发现 90% 时间耗在一个他自己都忘了的memset上——每轮循环清空一个 10^7 的数组循环 10^5 次那能不超时吗。2. 复杂度选错九成超时都死在这里2.1 一张表看懂数据范围和复杂度的对应关系这张表我建议每个刚开始刷题的人都存一份看题先看范围范围决定复杂度复杂度决定你能不能写。数据规模 n能承受的复杂度典型算法危险区n ≤ 10O(n!)全排列暴力无n ≤ 20O(2^n)状态压缩、子集枚举n 到 25 就悬n ≤ 100O(n³)Floyd、三重循环 DPn 到 500 必挂n ≤ 1000O(n²)普通 DP、双重循环n 到 5000 危险n ≤ 10^5O(n log n)排序、二分、线段树、堆O(n²) 绝对不行n ≤ 10^6O(n) 或 O(n log n) 偏紧线性扫描、前缀和常数大就挂n ≤ 10^8O(n) 且常数极小简单累加基本只存在于理论举个具体例子。一道题给n ≤ 10^5让你统计数组里有多少对(i, j)满足a[i] a[j]且i j也就是逆序对。很多人第一反应是双重循环long long cnt 0; for (int i 0; i n; i) for (int j i 1; j n; j) if (a[i] a[j]) cnt;这段代码逻辑完全正确但 n 10^5 时内层总共要跑约 5×10^9 次比较1 秒的判题机跑 10^8 次都费劲差了整整五十倍交上去必定 TLE。这时候不是优化常数能救的得换算法归并排序求逆序对或者树状数组离散化复杂度降到 O(n log n)n 10^5 时大约 1.7×10^6 次操作稳得很。我给个能直接用的归并版本long long ans 0; int tmp[MAXN]; void merge_sort(int l, int r) { if (l r) return; int mid l (r - l) / 2; merge_sort(l, mid); merge_sort(mid 1, r); int i l, j mid 1, k l; while (i mid j r) { if (a[i] a[j]) tmp[k] a[i]; else { ans mid - i 1; tmp[k] a[j]; } } while (i mid) tmp[k] a[i]; while (j r) tmp[k] a[j]; for (int p l; p r; p) a[p] tmp[p]; }这里mid - i 1是关键当右边元素小于左边元素时左边从 i 到 mid 的所有元素都和它构成逆序对。这个计数方式比循环里加一堆判断要快得多因为它是“批量结算”。2.2 嵌套循环里的重复计算最要命有些代码复杂度看着没问题但循环体里藏了重复劳动。最典型的三种第一种循环条件里反复调用函数。比如for (int i 0; i strlen(s); i)。strlen是 O(n) 的放在循环条件里整个循环就变成 O(n²)。n 10^5 的字符串直接超时。正确做法是先算出来存着int len strlen(s); for (int i 0; i len; i) { /* ... */ }注意 C 的std::string::size()是 O(1) 的不存在这个问题但 C 的strlen是实打实要扫到\0的。这个坑每年都能坑一大批人。第二种循环体内重复做同样的计算。比如for (int i 0; i n; i) { for (int j 0; j n; j) { sum a[i] * b[j] a[i] * c[j]; } }a[i]在内层循环里被取了两次虽然现代编译器多半会把它提到寄存器但在没有开优化或者编译器比较保守的情况下这就是白白多出来的内存访问。养成习惯能提的常量提到外层for (int i 0; i n; i) { int ai a[i]; for (int j 0; j n; j) sum ai * (b[j] c[j]); }第三种循环里调sqrt、pow、取模。这几个都是慢操作。sqrt一次大概几十个时钟周期放在 10^7 次的循环里就是灾难。如果只需要判断完全平方数用整数开方或者预处理表如果取模次数太多考虑先累加再统一取模只要保证中间不溢出就行。2.3 容器和数据结构选错等于自带减速带C 语言里选择没那么多但 C 写 OJ 的人越来越多这里面的坑也多。std::map每次插入、查找都是 O(log n)而且常数很大因为它是红黑树节点分散在堆上缓存极不友好。n 10^5 次操作map可能要跑几百毫秒换成排序加二分或者直接用数组下标做桶时间能掉一个数量级。unordered_map理论上是 O(1)但它有哈希冲突出题人如果存心卡构造一组冲突数据就能让退化到 O(n)所以关键题目上我一般不敢完全依赖它。std::vector的push_back在容量不足时会重新分配并整体拷贝虽然摊还复杂度是 O(1)但如果你预先知道大小一定要reservevectorint v; v.reserve(n); for (int i 0; i n; i) v.push_back(x);这一行reserve能省掉十几次重新分配和元素搬移在 n 10^6 的时候差别非常明显。还有一个隐蔽的坑二维数组的访问顺序。C 语言是行优先存储a[i][j]里 j 连续变化时是顺序访问内存缓存命中率高如果你写成a[j][i]每次跳一整行缓存基本全废同样的循环次数可能慢三到五倍。这个不是算法问题是硬件问题但对 TLE 的影响很实在。2.4 递归不是不能用但要看清楚代价递归写起来舒服代价是函数调用开销和栈空间。一次函数调用大概几十个时钟周期深度 10^5 的递归光调用开销就是几百万周期再加上每层压栈出栈很容易超时。更麻烦的是递归深度超过栈空间会直接崩。如果递归本身是指数级的比如朴素斐波那契int fib(int n) { if (n 1) return n; return fib(n - 1) fib(n - 2); }n 40 就要跑上亿次n 50 直接跑不完。这种必须加记忆化把算过的结果存数组long long memo[100]; int vis[100]; long long fib(int n) { if (n 1) return n; if (vis[n]) return memo[n]; vis[n] 1; return memo[n] fib(n - 1) fib(n - 2); }加上这两行复杂度从 O(2^n) 掉到 O(n)n 90 都是瞬间出结果。很多人以为自己是“递归超时”其实是“重复子问题没处理”本质还是复杂度问题。3. 算法对了还被卡常数优化的实战清单3.1 输入输出可能是你没算到的开销有些题目输入量极大比如 10^6 个整数甚至更多。这时候 I/O 的占比可能超过计算本身。cin和cout默认和 C 的stdio同步速度比scanf慢不少关掉同步能快好几倍ios::sync_with_stdio(false); cin.tie(nullptr);但注意关掉同步之后就不能混用cin和scanf了否则读入顺序会乱。另外endl会强制刷新缓冲区在循环里用endl输出 10^5 行那个刷新开销足够让你 TLE一律换成\n。如果连scanf都嫌慢可以上手写快读。原理是getchar逐字符读避开格式化解析的开销inline int read() { int x 0, f 1; int c getchar(); while (c 0 || c 9) { if (c -) f -1; c getchar(); } while (c 0 c 9) { x x * 10 (c - 0); c getchar(); } return x * f; }这里有个细节必须强调c要用int而不是char。因为getchar()返回的是intEOF 是 -1如果你用char接某些平台上char是无符号的EOF 会被截断成 255导致判断失效最后变成死循环 TLE。这个坑非常经典。输出同理如果输出量巨大可以用putchar手写输出或者攒到缓冲区一次性输出。不过大部分题目用printf就够了别过早优化先确认瓶颈在不在 I/O。3.2 多组数据下的清空操作是隐形杀手带多组数据的题目很多人习惯在每组数据开头来一发memset(a, 0, sizeof(a))。如果数组只有几千个元素无所谓如果数组是 10^7 的int一次就是 40MB 的内存写入而组数可能有 10^5 组总写入量 4TB别说 1 秒1 分钟都跑不完。正确思路是只清用到的那部分for (int i 0; i n; i) a[i] 0;n 是当前这组数据的实际规模通常远小于数组上限。这一改时间可能从 TLE 直接掉到几十毫秒。还有一种情况是用“时间戳”代替清空。比如标记数组vis[]与其每次全清不如开一个stamp[]记录每个位置最后一次被标记的组号判断时比较组号是否一致即可。这个技巧在并查集、图论题里非常常用属于老选手的基本功。提示看到题目里有T组数据且数组开得很大先把所有memset找出来这是超时的高发区。3.3 一份能照着改的常数优化清单下面这些手段不影响正确性纯粹是让同样的逻辑跑得更快。按性价比排序优化手段典型收益适用场景注意事项局部变量替全局变量中热点循环全局变量访问要走地址提常量到循环外中内层重复取值编译器不保证总能优化数组按行访问大二维 DP、矩阵缓存局部性reserve预分配中vector 大量 push_back只在知道大小时有效用\n替endl大大量输出endl 每次刷新手写快读大输入量 10^6 以上注意 EOF 判断用 int减少取模次数中循环内累加防溢出用位运算替乘除 2小极端卡常编译器多数已优化循环展开小极热点可读性下降明显预计算打表大多次查询固定值一次性开销转常数关于位运算我要泼一点冷水i * 2和i 1在现代编译器开 O2 的情况下生成的机器码通常一样指望这个救命不现实。真正有用的是减少内存访问和减少函数调用这两块才是常数的大头。还有一个常被忽略的点取模运算很慢。整数除法在 x86 上大概要 20 到 40 个时钟周期比加法慢一个数量级。如果循环里每次都% MOD累积起来很可观。可以改成累加到一个较大的阈值再取模或者用减法代替取模当模数固定且数值范围可控时。3.4 语言和编译选项的差异比你想的大同一份逻辑用 C 编译和用 C 编译跑出来的时间可能差 20% 到 50%。一般来说 C 的标准库更轻启动开销小纯计算题上略占优势但如果你的代码用了大量 C 容器那当然还是选 C。提交时看清楚平台的选项能选C (gcc)就别犹豫。本地测试时记得开和判题机接近的优化等级。很多人本地用默认的-O0测程序跑 3 秒吓得去改算法实际上判题机用-O2跑起来只有 400ms。反过来本地开-O2测得很美判题机没开优化照样 TLE。这个信息一般在平台的帮助页面能查到花两分钟看一眼能省掉大量误判。gcc -O2 -stdc11 -o prog prog.c另外编译选项里的-static、栈大小设置这些一般平台是固定的你改不了但知道它们存在有助于理解为什么同一份代码在不同平台表现不同。4. 几个真实改造过程的复盘4.1 案例一从双重循环到树状数组有个同学拿来一段代码题目是统计区间内小于等于某值的元素个数n 10^5查询 q 10^5。他写的是每次查询扫一遍区间for (int i 0; i q; i) { int cnt 0; for (int j l[i]; j r[i]; j) if (a[j] x[i]) cnt; printf(%d\n, cnt); }复杂度 O(nq) 10^10必挂。改造成离线处理加树状数组把所有查询按 x 排序把数组元素也按值排序逐个把小于等于当前 x 的元素插进树状数组然后区间查询就是两次前缀和相减。复杂度 O((nq) log n)10^5 规模下大约 3×10^6 次操作跑 100ms 出头。这个改造的关键不是树状数组本身而是把“每次重新扫”变成“增量维护”。很多超时题的破局点都在这里你有没有办法把重复计算的部分缓存下来。4.2 案例二字符串拼接的隐藏二次方另一个典型是字符串处理。有人这么写char s[100005] ; for (int i 0; i n; i) { char t[2] {c[i], \0}; strcat(s, t); }看起来每次只追加一个字符但strcat每次都要从s的开头扫到结尾找\0第 i 次追加要扫 i 个字符总共 O(n²)。n 10^5 时是 5×10^9 次字符访问稳稳超时。改法很简单维护一个长度指针int len 0; for (int i 0; i n; i) s[len] c[i]; s[len] \0;同样的效果O(n)。C 里对应的是不要在循环里写s s ch用s.push_back(ch)或者先reserve再追加。4.3 案例三图论题用邻接矩阵的代价一道 n 10^5、m 2×10^5 的图论题有人开了int g[100005][100005]。先不说时间这个数组本身就要 40GB 内存编译都过不了。就算把 n 缩小到 5000矩阵是 25×10^6 个 int100MB也超内存了。正确做法是邻接表。C 语言用数组模拟int head[MAXN], nxt[MAXM], to[MAXM], ecnt 0; void add_edge(int u, int v) { to[ecnt] v; nxt[ecnt] head[u]; head[u] ecnt; }遍历时顺着head[u]一路走nxt。这个写法比vectorint g[MAXN]更快因为内存连续、没有动态分配开销而且缓存友好。在 10^5 级别的图上这个差别能到两倍以上。4.4 案例四一份被 memset 拖死的代码最后这个案例特别有代表性。代码逻辑是标准的 BFSn 10^5m 2×10^5理论上完全跑得动。但他每组数据开头都有memset(vis, 0, sizeof(vis)); memset(dis, 0, sizeof(dis)); memset(head, -1, sizeof(head));三个数组加起来大概 2MB 多单次清空不到 1ms看起来不多。但题目有 10^4 组数据总计就是 20GB 的内存写入20 秒起步。改法vis用时间戳dis只清1..nhead只清1..n。改完之后总时间从 20 秒掉到 200ms。这个案例我印象特别深因为它说明超时不一定出在循环里也可能出在循环外面的初始化而初始化往往最容易被忽略因为大家潜意识里觉得“清个数组能有多慢”。5. 超时排查速查表与踩坑经验5.1 一张表覆盖八成超时场景现象最可能的原因快速验证方法解决方向小数据能过大数据 TLE复杂度过高按数据范围估算运算量换算法所有数据都 TLE包括样例死循环本地跑样例看是否卡住查循环变量、EOF 判断本地快提交慢编译优化差异、机器差异本地开 -O2 重测换语言、压常数多组数据越跑越慢初始化范围过大注释掉 memset 再测只清有效部分输入特别大时 TLEI/O 瓶颈换 scanf / 快读对比优化输入递归题 TLE重复子问题、深度过大加计数器统计调用次数记忆化或改迭代图论题 TLE 或 MLE邻接矩阵看数组大小改邻接表字符串题 TLE反复 strlen、strcat检查循环条件缓存长度、指针追加排序后 TLE用了低效排序换 std::sort 对比用库函数随机数据能过特定数据 TLE哈希冲突、退化换数据结构避开 unordered_map5.2 那些“不是超时却被判超时”的坑有几个情况特别冤明明代码没问题就是过不了。第一输出格式导致的超时。有些平台的比对程序在遇到格式不符时会反复重试读取表现成超时。比如题目要求每行末尾不能有空格你多打了一个空格可能不是 PE 而是 TLE。这类问题只能靠仔细看输出要求或者用diff本地比对。第二文件读写没关。极少数题目要求从文件读写如果你开了文件流但没关闭缓冲区不刷新程序结束时可能卡在刷新上。虽然少见但遇到了很难查。第三while循环里的scanf返回值没判断。前面提过while (scanf(%d, n))在输入结束后返回 0循环不退出直接死循环。正确写法是判断! EOF或者 1。这个错误的隐蔽性在于样例输入正常结束程序就跑完了看起来没问题但判题机可能有多组测试文件或者输入末尾没有额外换行就卡住了。第四随机数种子用了时间。极少数题目需要随机化算法如果种子用time(NULL)在某些沙箱环境里时间不变导致每次跑出一样的结果陷入退化路径表现成超时。这种情况改成固定种子反而更稳。第五递归深度刚好卡在边界。深度 10^5 的递归在某些平台栈空间够在某些平台不够表现可能是 RE 也可能是 TLE。稳妥起见深搜超过 10^5 层就考虑改迭代或者手动开栈。5.3 我自己的几条保命习惯最后分享几条我常年刷题养成的习惯都是被坑出来的。看题先看数据范围再看时间限制最后看内存限制。这三个数字决定了这道题的解法上限比题目描述本身还重要。数据范围 10^5 就是告诉你“别写 O(n²)”时间限制 1000ms 就是告诉你“常数别太浪”。写完先本地造极限数据。别用样例自测样例通常是最弱的。自己写个小脚本生成 n 10^5 的随机数据跑一遍计时心里就有数了。生成数据用 Python 或者 shell 都行几行代码的事python3 -c import random n 100000 print(n) print( .join(str(random.randint(1, 10**9)) for _ in range(n))) big_input.txt提交前把调试输出全删干净。有人留着printf在循环里输出到标准输出一方面拖慢速度另一方面污染答案。调试信息一律走stderr这是底线。不要迷信“再交一次”。判题机的负载确实会波动同一份代码可能这次 TLE 下次 AC但这只对临界情况成立。如果你的代码超时 3 倍以上重交一百次也没用。判断标准很简单本地开 O2 跑如果比时间限制高出很多就别浪费提交次数了。遇到玄学先怀疑自己。我见过太多人抱怨“平台卡我”最后一查是自己数组越界写坏了内存、或者循环边界差一。判题机是死的它不会针对你。真觉得数据有问题先把代码贴出来让人看大部分时候问题一眼就能被发现。保持一份自己的模板。快读、快写、常用宏、常用数据结构整理成一个文件每次开题直接复制。这不能解决算法问题但能让你少在重复劳动上犯错也少在 I/O 上浪费时间。模板这东西越用越顺手改着改着就变成自己的了。上面这些内容涵盖了从判断超时性质、估算复杂度、定位瓶颈、到具体优化手段的完整链条。真正上手的时候你会发现大部分 TLE 其实在第一步就能定性数据范围一摆出来该不该换算法就清楚了。剩下的常数优化属于锦上添花能压则压但别指望它救一个复杂度错误的方案。