OJ基础题避坑指南：排序、辗转相除法与字符统计细节解析

最近在某高校OJ平台刷基础题，做到第7题到第9题的时候，突然被几个平时不太注意的细节卡住了。这三道题本身难度不大，但涉及排序、数学算法、字符处理，属于典型的OJ基础题模板。当时我把题解发给一个刚开始刷题的朋友，他看完说“原来填空题级别的题也有这么多门道”。我整理了一下，把这三道题的完整分析、代码、坑点一次性写清楚，给正在刷类似OJ基础题的朋友做个参考。

1. 题目概览与题型拆解

1.1 第7题：三数从小到大排序

第7题的原题描述很常见，大意是“输入三个整数，按从小到大顺序输出”。题目看起来简单，但它在OJ基础题里的地位很特殊，它引出了排序最基础的交换思想和比较逻辑。很多新手会直接写三个if，却没有意识到这已经是在手写排序算法了。

我当时的做法是先把题目要求掰开看：输入格式是同一行三个整数，还是三行各一个整数？输出要求是数字之间用空格分隔，最后有没有多余回车？这些都会影响最终提交。

这类题的考察点有三个：

• 能不能正确进行两个数的比较和交换
• 能不能处理数字相等的情况
• 能不能严格按照输出格式写出结果

实际写的时候，最容易出问题的不是排序逻辑，而是“管住换行和空格”这件事。后面会在第3章专门说。

1.2 第8题：最大公约数和最小公倍数

第8题典型描述是“输入两个正整数，输出它们的最大公约数和最小公倍数”。这道题在算法层面比第7题上了一个台阶，因为直接暴力的穷举虽然能过，但效率低，而且容易被边界值坑到。用辗转相除法才是正规军的做法。

这道题的隐藏考点包括：

• 是否理解最大公约数（GCD）和最小公倍数（LCM）之间的数学关系
• 是否知道辗转相除法（欧几里得算法）的原理和实现
• 是否注意到乘法溢出问题

很多教科书里会直接给出公式：最小公倍数等于两数乘积除以最大公约数。但放在代码里，如果直接用a * b / gcd，当a和b都是比较大的int时，a * b可能溢出，结果直接变成负数。这一点是第8题真正的得分点，后面会详细说。

1.3 第9题：统计各类字符个数

第9题常见描述是“输入一行字符，统计其中英文字母、数字、空格和其他字符的个数”。这是字符处理类的入门题，考察点很有意思：不是算法，而是对输入流的理解。

你需要明确“一行字符”的末尾到底有没有换行符，字符分类时是按ASCII码还是按字符范围，空格算一个分类，那Tab制表符算不算？这些细节在题目描述里写得很清楚，但实际用scanf("%s")去读会直接漏掉空格，所以必须用getchar()或者fgets()。

我当时在这一题卡住，就是因为用scanf读了字符串，结果输入“hello world”它只读到了“hello”，统计完全不对。后来老老实实改用getchar()逐个读字符，才解决。

2. 代码实现与核心细节

2.1 第7题：三种实现方式，选哪种最稳

先把三种常见写法都摆出来，看看各自的优缺点。

第一种，最直白的“三个if交换”：

#include <stdio.h> int main() { int a, b, c; scanf("%d %d %d", &a, &b, &c); if (a > b) { int t = a; a = b; b = t; } if (a > c) { int t = a; a = c; c = t; } if (b > c) { int t = b; b = c; c = t; } printf("%d %d %d\n", a, b, c); return 0; }

三个if的顺序必须固定：先保证a最小，再保证b比c小。我当时一个同学写成了if判断a>b然后a>c、b>c的乱序，结果数据一换顺序就出错。原因在于，排序要“每次把最小的放到最前面”，顺序不能随意调换。

第二种，冒泡排序思想，适合以后扩展：

#include <stdio.h> int main() { int a[3]; scanf("%d %d %d", &a[0], &a[1], &a[2]); for (int i = 0; i < 2; i++) { for (int j = 0; j < 2 - i; j++) { if (a[j] > a[j + 1]) { int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; } } } printf("%d %d %d\n", a[0], a[1], a[2]); return 0; }

这种写法虽然代码量多一点，但它把“比较次数”和“交换逻辑”拆开了，就算题目扩展成四个数、五个数也能用。我在OJ上提交的是第一种，因为三个数的题目用if交换更清晰，而且速度更快。

第三种，写一个交换函数来封装：

#include <stdio.h> void swap(int *x, int *y) { int t = *x; *x = *y; *y = t; } int main() { int a, b, c; scanf("%d %d %d", &a, &b, &c); if (a > b) swap(&a, &b); if (a > c) swap(&a, &c); if (b > c) swap(&b, &c); printf("%d %d %d\n", a, b, c); return 0; }

函数封装虽然简单，但一定要记得传指针。很多初学者写swap(a, b)然后发现值没变，就是因为函数参数是值传递，修改只在函数内部生效。这也是一个常见考点。

2.2 第8题：辗转相除法的实现与溢出陷阱

先给出最基本的辗转相除法，用迭代实现：

#include <stdio.h> int gcd(int a, int b) { while (b != 0) { int t = a % b; a = b; b = t; } return a; } int main() { int a, b; scanf("%d %d", &a, &b); int g = gcd(a, b); int lcm = a / g * b; printf("%d %d\n", g, lcm); return 0; }

这里有一个关键细节：计算最小公倍数时，我写的是a / g * b，不是a * b / g。原因是a * b可能在int范围内溢出，导致结果变成负数或截断后的错误值。先用a / g，把其中一个数缩小到安全范围，再乘b，就能避免大部分溢出问题。

举个例子，如果a = 2000000000，b = 3000000000，int的最大值是2147483647，a * b显然溢出。但a / g * b，因为g至少是1，所以结果可能仍大，这时候其实应该用long long。所以在碰到两个较大的数时，我建议直接这样写：

long long lcm = 1LL * a / g * b;

用1LL把整个计算提升为long long类型，再输出时用%lld。

另外，递归写法也可以，但要注意递归深度一般不会太大，两个int范围内的数，辗转相除的递归深度最多几十层，没压力：

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

如果OJ编译器支持C99，这种写法很简洁，但要注意b为0时返回a，也就是最大公约数是那个非零本身。

关于边界：输入的两个正整数中如果有1，那么最大公约数是1，最小公倍数是另一个数。如果两个数相等，最大公约数和最小公倍数都是它本身。这些用例我后来都放进自测表里了。

2.3 第9题：字符统计的完整代码与读取方式

第9题的正确做法是靠getchar()循环读取，而不是一次性读入字符串。

#include <stdio.h> int main() { char ch; int letters = 0, digits = 0, spaces = 0, others = 0; while ((ch = getchar()) != '\n' && ch != EOF) { if ((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z')) { letters++; } else if (ch >= '0' && ch <= '9') { digits++; } else if (ch == ' ') { spaces++; } else { others++; } } printf("%d %d %d %d\n", letters, digits, spaces, others); return 0; }

这段代码有几个细节要说明：

• 循环条件ch != '\n' && ch != EOF，同时处理了换行和文件结束两种情况。有的题目说“输入一行”，但实际评测数据可能在行尾有换行，也可能没有。单独判断\n会在没有换行时继续读到EOF，导致多统计一个EOF？不会，但加上EOF判断更稳。
• getchar()返回的是int，不是char。虽然赋值给char能存ASCII码，但在判断EOF时，如果EOF是-1，可能被截断。所以更严谨的写法是把ch声明为int：

int ch; while ((ch = getchar()) != '\n' && ch != EOF) { // 用ch判断 }

• 如果题目要求统计所有字符串包含空格，那用scanf("%s")就废了。也可以用fgets读一行再遍历，但要注意fgets会保留换行符，需要单独处理。

我当时用getchar()也踩了一个坑：如果前面用scanf读过整数，再用getchar()读字符，那scanf留下的换行符会被getchar()先读走，直接导致统计结果少一个字符。解决办法是读整数后先getchar()把换行吞掉，或者统一用fgets。

3. 避坑指南：OJ评测的隐藏规则

3.1 多组输入与EOF处理

第7到第9题，有的OJ版本会要求“输入多组数据，每组占一行，直到文件结束”。这时候如果你只写一次输入，提交后就会卡在“只通过了部分测试数据”，报错往往是Wrong Answer。

正确套路是套一个while循环：

int a, b, c; while (scanf("%d %d %d", &a, &b, &c) != EOF) { // 处理每组数据 }

注意，scanf返回的是成功读入的字段数量。如果你想更严谨，可以写成：

while (scanf("%d %d %d", &a, &b, &c) == 3) {

这样能保证三个数都成功读到了才进入循环。这两个写法的区别在于：EOF写法在输入数据不完整时也会进入循环，而== 3更严格。我在实际刷题时遇到过一次输入文件末尾有一个空行，用!= EOF会多读一次，导致输出多一行。后来改成== 3就AC了。

3.2 边界值和极端值测试

基础题最容易失分的不是算法，而是边界值。我整理了一个自测表，每道题提交前都过一遍：

这些用例看起来简单，但每一个都对应一类隐藏问题。比如第7题的负数，如果只用if交换但没考虑等于号，可能会在a=b时错误交换，导致结果改变。

3.3 输出格式别大意

OJ评测机是逐字符比对结果的，多一个空格、少一个换行、行尾多一个空格，都会报“格式错误”或“答案错误”。第7题要求三个数之间用空格隔开，末尾要不要换行？大多数OJ要求有换行，但有的不强制。最稳妥的写法是：

printf("%d %d %d\n", a, b, c);

末尾带一个换行，这是绝大多数OJ的通用惯例。如果你发现居然PE了，再看一下题目是不是要求“每个输出占一行”。

还有一种情况：输出多组数据时，每组之间要不要多空一行？像第8题如果多组输入，一般每组输出一行，不需要空行。但如果题目说“每组输出后带一个空行”，那就要在每组后面多打一个\n。这种细节只能靠读题。

3.4 编译报错常见原因

基础题报错最多的不是逻辑，而是编译错误。我见过同行同学栽在这些地方：

• scanf("%d", a);忘了写&，编译报错或者运行崩溃
• 变量声明放在了使用之后，老编译器不支持C99的声明位置
• 用中文标点写代码，比如printf(“%d”, a);用了中文引号，编译直接报错
• 头文件没写#include <stdio.h>，用了printf不声明
• main函数返回类型写成了void，在部分OJ上能过，但在严格要求C标准的环境下会警告甚至CE

针对这些，我建议不管题目多简单，都先用本地编译器跑一遍，至少保证没有警告再提交。

4. 问题排查与调试技巧

4.1 本地正确但OJ报Wrong Answer的排查思路

这种问题几乎每个刷OJ的都遇到过。我当时做题的正确率不高，后来总结出一个固定排查流程：

第一步，先看题目是否有多组输入。把代码里的scanf包进while循环里再试。

第二步，检查输出格式。别信自己眼睛，用肉眼看看最终输出的字符串长什么样。可以在本地把输出重定向到文件，然后用cat -A（Linux）或type（Windows）看有没有多余空格。

第三步，检查变量类型。两个int相乘，结果存到int里？那大概率溢出。字符统计里，getchar()返回的EOF是-1，用char接收会变成255，和你预期的EOF完全不同。

第四步，检查逻辑顺序。比如三数排序，if的数量和顺序有没有覆盖所有情况？可以用全排列测试：把1,2,3所有排列都输一遍，看输出是否一致。

第五步，提交之前把printf调试输出全部删掉。有同学在代码里留了printf("a=%d\n", a);，OJ比对结果时发现多了一堆字符，直接WA。

4.2 用几组“刁钻”数据自测

除了前面表格里的边界用例，我还会用一些“故意找茬”的数据。比如第7题，输入：

2 3 2

如果代码里用的是if (a > b)这种写法，当a == b时不会交换，输出是2 3 2，这没问题。但如果有人写了if (a >= b)且没有后续修正，可能输出成2 2 3，那就错了。所以自测时一定要覆盖“有相等值”的情况。

第9题，输入纯空格时，有的人会统计成0 0 1 0（因为读到了末尾换行？），实际上空格是三个，输出应该是0 0 3 0。这说明循环条件里要区分空格和换行，换行符不能计入空格。

还有一组很阴险的数据，输入字符串中间有多个连续空格，比如a b，中间有两个空格。有的写法用scanf读字符串会直接漏掉b，输出错误。用getchar则没问题，因为你是一个一个读的。

4.3 临时调试输出和freopen的用法

调试OJ代码，我有两个习惯：

第一个习惯，用freopen从文件读入，避免每次手动输入数据。在代码开头加一句：

freopen("test.in", "r", stdin);

然后把测试数据放在test.in文件里。提交前删掉这行或者注释掉。注意，有的OJ不支持freopen？本地调试没问题，提交前删掉就行。

第二个习惯，在关键位置临时打印变量值。比如第8题，我想知道gcd函数里每一步a和b的变化，就在循环里加printf：

while (b != 0) { printf("before: a=%d b=%d\n", a, b); int t = a % b; a = b; b = t; }

看明白后再删掉。这比空想快很多。

这两个习惯帮我至少节省了三分之一的时间，因为很多错误一眼就能看出来，不需要反复提交浪费等待时间。

5. 从基础题里提炼的通用经验

这三道题每道都很基础，但我做完之后发现，它们正好覆盖了OJ题里最核心的三个能力：处理输入输出、处理边界条件、处理类型溢出。很多人觉得基础题只是“热身”，但我在实际刷题中看到大量重复WA，恰恰就是死在基本功上。

比如第7题，如果你能把三个if的交换顺序讲明白，后面学冒泡排序、选择排序都会更快。第8题，你不光要会背辗转相除法，还要理解为什么先除后乘能防溢出。第9题，你要分清getchar和scanf的差别，理解缓冲区里残留的换行符是怎么影响后续输入的。这些放到更难的题里，就是“题目读懂了一半”和“真正能做出来”的分水岭。

我后来有一个习惯：每刷一套基础题，都会把它的输入输出格式、边界情况整理成笔记。等遇到相似的题目，直接翻笔记对照，省了不少力气。比如第8题做多了，我看到“输入两个正整数，求公约数公倍数”就知道要考虑溢出，看到“输入一行字符”就知道不能用scanf("%s")。

这份笔记我至今还在用，虽然现在刷的题难度高了不少，但很多套路还是从这些基础题里长出来的。

如果你现在也卡在OJ基础题的7到9题上，别急着搜答案，先按我说的几个步骤自己过一遍：读题看清楚输入输出格式，想清楚边界值，再动手敲代码，最后用几组刁钻数据自测。这样一遍下来，你收获的绝对不只是“AC”两个字。