企业官网建设流程全解析

信息奥赛课课通 C++ 分册的 p154-1“近似排序”，是一道看上去简单、实际上特别能暴露基本功的题。我第一次拿到这个题名的时候也愣了一下：排序就排序，什么叫“近似排序”？难道是允许差不多排一排就行？等看完数据范围和要求才反应过来，这个“近似”是有讲究的：输入一串正整数，要先把每个数的十进制表示倒过来得到一个“镜像值”，再拿这个镜像值去排序，镜像值相同的还要按原数大小再排一次，最后输出的却是原数。整道题下来，C++ 的 sort、自定义比较规则、数的拆合、结构体封装全都过了一遍，非常适合正在刷信息奥赛入门题、准备 CSP-J/S，或者刚把 sort 当黑盒用的人拿来练手。

1. 先看题目到底在考什么

1.1 “近似排序”里的“近似”体现在哪

常规排序直接用元素本身的大小比较，1、5、23、14 排出来是 1、5、14、23。但题目换成“反转后再比”，23 和 14 反转后分别是 32 和 41，于是 23 要排在 14 前面，排出来就变成了 1、5、23、14。表面上看起来“乱序”，其实规则一换，排序依据就完全变了。

这里的“近似”两个字特别关键。排序的键值不是原始值，而是原始值经过一个变换函数之后的产物。所以最终数组相对普通数值排序来说，只是“大概有序”。这种题在信息奥赛里非常经典，它考的不是你会不会调用 sort，而是你能不能读懂题面里那句“按某某转换后的值排序”。很多同学只背了 sort 的升序降序用法，遇到这种题目就蒙，本质是没有理解排序真正接受的是一个“比较规则”，而不是一个固定的数值方向。

想明白这一点，后面所有代码都是在翻译这句话：把“反转值小的站前面，反转值一样就原数小的站前面”变成 sort 能听懂的规则。

1.2 把题目翻译成程序要做的四件事

读题之后我会先把任务拆成四步，这是解一切排序题的基本功。

• 第一步，读入数据。题目会先给一个 n，然后给 n 个正整数，这里用数组或 vector 存下来就行。
• 第二步，对每个数求反转值。这一步是核心加工逻辑，需要一个专门写反转数字的函数。
• 第三步，排序。排序规则不是直接比原始值，而是先比反转值，反转值相同再按原始值从小到大排。
• 第四步，输出。注意输出的是原数，不是反转后的数，这是新手最容易丢分的地方。

这四步缺一不可。我在机房里见过太多人盯着“怎么反转数字”死磕，结果第三步用错了比较键，要么输出是一串反转值，要么自己看着对但提交 OJ 就是判错。先把流程理清楚，写代码就是在做翻译，难度直接降一半。

1.3 对应到的知识点清单

这道题覆盖面其实相当广，我列了一个简单的对照表，可以当作自测清单：

这些内容基本就是入门阶段“排序”这一章的所有核心能力点。你要是能把这道题完整独立写出来，说明你已经不是单纯背代码的阶段了，而是真的理解了 sort 的工作方式。顺带一提，反转数字这个动作本身也很有用，很多题目都会用到，比如判断回文数、数字各位求和等等，练熟这一手不亏。

2. 两种主流实现方案

2.1 方案一：sort 加自定义比较函数

最简单直白的做法是开两个数组，一个存原始值 val[]，一个存反转值 rev[]，排序的时候把 cmp 函数写在 sort 的第三个参数里。

bool cmp(int x, int y) { int rx = reverseNum(x), ry = reverseNum(y); if (rx != ry) return rx < ry; return x < y; } sort(a, a + n, cmp);

注意这个写法里，cmp 每次比较都要现算一次反转值。数据量小的时候完全没问题，但你要清楚这里的代价：sort 的平均比较次数是 O(n log n)，每个数每次比较又要做一次 O(位数) 的循环，整体复杂度会变成 O(n log n * 位数)。如果题目把 n 放到 10 的 5 次方以上，这个现算的写法其实是可以优化的。

不过说实话，这道题本身的 n 一般不大，这样写也能过。真正的问题在于代码可读性一般，你以后想再加条件就很别扭，而且两个数组的索引关系一旦搞乱，调试会非常痛苦。

2.2 方案二：结构体打包

我更推荐的做法是把原数和反转值打包进一个结构体，预处理一次反转值，然后排序时直接比较结构体里的 rev 字段：

struct Node { int val; int rev; }; bool cmp(const Node &a, const Node &b) { if (a.rev != b.rev) return a.rev < b.rev; return a.val < b.val; }

预处理阶段把 rev 算好存进去，排序阶段 cmp 里就不用再重复计算。代码逻辑一下子清楚很多，而且结构体天然解决了“要同时带着原数和反转值走”的问题。排完之后，你既能拿到原数用于输出，也能拿到反转值做校验，不用担心两个数组对应错位。

这个方法在信息奥赛里是标准做法，因为结构体 + 自定义排序在后面的贪心题、结构体排序题里到处都用，早学会早受益。

2.3 两个方案的取舍

我把两种方案放在一起对比：

如果只是手搓一个小程序验证思路，方案一足够了。但如果你想在比赛里稳定拿分，我建议直接养成结构体的习惯。还有一个折中办法，如果你嫌结构体麻烦，可以用 pair 容器，pair 排序会先比 first 再比 second，天然支持两关键字，前提是你得把“反转值放 first、原数放 second”想明白。不过 pair 的名字不够直观，比赛自查的时候容易看晕，我还是偏向结构体。

3. 完整参考代码与细节讲解

3.1 一版可以直接提交的代码

下面这版代码是完整可运行的，我加了详细注释，核心逻辑一目了然：

#include <bits/stdc++.h> using namespace std; struct Node { int val; // 原始值 int rev; // 反转后的值 }; int reverseNum(int x) { int r = 0; while (x > 0) { r = r * 10 + x % 10; x /= 10; } return r; } bool cmp(const Node &a, const Node &b) { if (a.rev != b.rev) return a.rev < b.rev; return a.val < b.val; } int main() { int n; cin >> n; vector<Node> a(n); for (int i = 0; i < n; i++) { cin >> a[i].val; a[i].rev = reverseNum(a[i].val); } sort(a.begin(), a.end(), cmp); for (int i = 0; i < n; i++) { if (i) cout << ' '; cout << a[i].val; } cout << endl; return 0; }

头文件直接用#include <bits/stdc++.h>是信息奥赛的通用习惯，它会一次性把常用标准库都包含进来，比赛环境下能少记很多头文件名字。你要是用 Dev-C++ 或者 Visual Studio 写作业，这个头文件一般也支持，但如果你们的 OJ 比较老，个别环境可能需要改成具体头文件，比如#include <iostream>加上#include <algorithm>和#include <vector>。

提示：reverseNum这个名字是我从reverse（反转）来的，网上也有人写成reserveNum，但reserve在容器里是“预留空间”的意思，语义完全不同，命名最好别混。

3.2 核心函数 reverseNum 的写法

反转数字的原理其实特别简单，就是不断取出个位，然后把已有的结果往左推一位。拿 123 举例：

123 % 10 = 3，r = 3，x = 12 12 % 10 = 2，r = 32，x = 1 1 % 10 = 1，r = 321，x = 0

循环结束后 r 就是 321。这里r = r * 10 + x % 10里的r * 10就是在把旧数字往高位挪，腾出个位的位置。这个套路在进制转换、数位分离里反复出现，属于信息奥赛的“肌肉记忆”级别操作。

有个很多人担心的点：120 反转后应该是多少？题目里的意思其实就是 21。因为从个位开始取，120 第一次取到 0，r 还是 0，第二次取到 2，r 变成 2，第三次取到 1，r 变成 21。前导零在这个过程中被自然丢掉了，不需要额外处理。你只要不在输出的时候补零，就不会出错。

3.3 容易被忽略的边界条件

我踩过好几次坑，这里集中讲一下。数据范围是最容易被忽视的：如果原数能到 10 亿级别，反转之后也可能到 10 亿级别，虽然 int 最大约 21 亿，但万一题目数据顶着上限出，反转时r * 10那一下就可能溢出。保险起见，要么在函数里用 long long 接收和返回，要么直接给结构体里的 rev 定义成 long long。多做这一步不会扣分，但能避免在极端数据上翻车。

n 等于 1 时，排序不会触发比较，直接输出原数，程序要能正常跑。重复值处理也比较关键，如果两个数的原值和反转值都相等，比如 3 和 3，那它们顺序随便，可是你的 cmp 里一定不能在相等时返回 true，这一点下一节细说。最后一个不是题目本身的边界，而是输出格式：OJ 一般允许行尾有空格，但如果你用循环直接cout << a[i].val << " "，最后一个数后面会跟一个空格，多数 OJ 不判错，可有些严格要求格式的题目会 WA。用我上面代码里的if (i) cout << ' ';就永远不会多空格。

4. 常见错误与调试实录

4.1 比较函数写成“<=”导致运行错误

这个错误我在带学生的时候见得太多了。sort 要求第三个参数是一个“严格弱序”的比较规则，通俗说就是：判断“谁该排在谁前面”的时候，两个相等的元素不能互相都说对方该在前面。如果你写成：

bool cmp(const Node &a, const Node &b) { if (a.rev != b.rev) return a.rev < b.rev; return a.val <= b.val; // 错误示例 }

当a.rev == b.rev且a.val == b.val时，a <= b返回 true，反过来b <= a也返回 true。sort 内部会觉得 a 排在 b 前面，同时 b 也排在 a 前面，逻辑直接乱套。实测表现可能是 RE（运行错误），也可能是 TLE（超时），还有可能只是结果顺序诡异。

解决办法很简单，任何比较函数里一律只在明确小于的时候返回 true，等于和大于的情况一律返回 false。这是写 cmp 的黄金法则，记牢它，能避开 C++ 排序里最经典的一类坑。

4.2 忘掉第二关键字

题目里明确写了“反转值相同按原数从小到大”，这个第二关键字不是可有可无的。sort 本身不稳定，也就是说两个元素的比较键值相同的时候，它们的相对顺序在排序后是没有保证的。如果你只写：

return a.rev < b.rev;

而不去管 val，那么反转值相同的那一组数，输出顺序完全看 sort 内部怎么折腾。数据一多，可能上一次对，下一次就错。

这里有个进阶认知：凡是题面出现“如果有多个……按……顺序输出”这种描述，就是要你显式加第二、第三关键字。与其依赖stable_sort保序，我更喜欢直接在结构体里多放一个 index 字段，排序时第三关键字比 index，这样无论 sort 还是 stable_sort 结果都完全确定，后文变式里我会给例子。

4.3 输出了 rev 而不是 val

这个错误低级，但几乎每学期都能抓到一两个。写排序的时候一直在用 rev 字段，排完序后顺手就cout << a[i].rev了，结果样例输出全是反转值，提交必 WA。想避免这个问题，最土的办法就是输出前在草稿纸上标清楚哪个字段才是题目要的答案。题目要输出的是原数，不管中间怎么比，最后一手一定要回到 val。

另外我习惯在本地写完代码之后，手动构造一组能验证第二关键字的数据。比如输入5 1 5 23 14 73，手算一遍排序结果是 1、5、23、14、73，然后用代码跑一遍对照。凡是这种“输出长得像乱序”的题目，手算对照的价值极大，比你盯着屏幕瞎猜效率高得多。

4.4 OJ 输入输出细节与本地验证

有些题面会写有多组测试数据，如果没写，就按单组处理。判断方法很简单：看样例输入是只给一个 n 开头，还是while (cin >> n)能连续读到 EOF。p154 这道题正常是单组，但你要是把多组逻辑写进去也不会错，只是没必要。

还有一个非常隐蔽的坑：如果某个测试点里输入的 n 后面有换行、空格，用cin >> n都不会有问题，因为它会自动跳过空白字符。真正要注意的是输出换行，最后一行之后一般要有一个endl或'\n'，不然个别 OJ 的老式判题器会报 Presentation Error。本地自测时我一般把输入输出都重定向到文件，a.in和a.out对比样例，效率比自己往终端里敲高很多。

5. 从这道题延伸出去：自定义排序的三种变式

5.1 变式一：按数位和排序

假设题目改成“按每个数的各位数字之和从小到大排序，如果数字和相同，按原数从小到大”，思路完全一样，只是把反转函数换成数位和函数：

int digitSum(int x) { int s = 0; while (x > 0) { s += x % 10; x /= 10; } return s; }

比较规则变成先比 digitSum，再比原值。你会发现代码模板不用大改，只换了加工函数和 cmp 里的字段。这种“换汤不换药”的题在信息奥赛里特别多，你要是能自己列出三五个类似的变换规则，比如按奇偶性排、按质因数个数排、按二进制中 1 的个数排，那这章基本就吃透了。

5.2 变式二：分数排序，交叉相乘避免浮点误差

再进阶一点，给 n 个分数（分子分母都是整数），按分数真值从小到大排序。很多人的第一反应是转成 double 再比，但在信息奥赛里，浮点精度和判题器的误差设置永远是不可控因素。更稳的方案是交叉相乘：

bool cmp(const Node &x, const Node &y) { // x.a / x.b < y.a / y.b return x.a * y.b < y.a * x.b; }

这个式子的数学依据很简单：两边同时乘以x.b * y.b，因为分母都是正整数，不等号方向不变。于是浮点比较变成了整数乘法比较，精度零损失。这道变式能帮你建立一种意识，cmp 里不只是能写简单的小于号，你可以在里面做任何数学化简。

5.3 变式三：显式下标，彻底解决稳定排序问题

如果题目要求“比较键值相同的时候，保持输入顺序”，最稳的写法是给结构体加一个 idx 字段：

struct Node { int val; int rev; int idx; }; bool cmp(const Node &x, const Node &y) { if (x.rev != y.rev) return x.rev < y.rev; if (x.val != y.val) return x.val < y.val; return x.idx < y.idx; }

这样即使 sort 内部不稳定，你的输出顺序也是确定的。以后在工作里做多级排序也同理，Java 里比较器、Python 里 sort 的 key 函数都是同一个思想，只是语法不同。把这道题吃透，等于把“排序规则”这个概念彻底打通了。

5.4 这类题的核心启示

我发现很多初学者会陷入一个误区，觉得排序题就是背模板，升序用sort(a, a+n)，降序加greater<int>()。但信息奥赛真正考察的是“怎么把题面的一句话翻译成比较规则”。你以后遇到优先队列、set、map 自定义顺序，甚至图论里按边权排序，思路都是从这道 p154-1 长出来的：加工出键值、装进结构体、写清 cmp、按需输出。把这个套路自动化，比刷十道纯升序降序都顶用。

代码风格上再做一点补充：如果你们 OJ 支持 C++11，cmp 也可以写成 lambda 表达式，例如sort(a.begin(), a.end(), [](const Node &x, const Node &y){ ... });，这样能将比较逻辑直接放在调用处，阅读上更连贯。不过比赛时我个人还是习惯写普通函数，因为报错信息更好定位，新手也更友好。

我个人在实际操作中的体会是，p154-1 最值钱的地方不在那两行 sort，而在它逼着你把“题目规则”翻译成“代码规则”的过程。信息奥赛的题目很少会让你背模板，它更喜欢给你一个稍微变形的场景，看你有没有真正理解底层机制。遇到这种题别急着敲代码，先拿笔在草稿纸上写一遍“谁排谁前面”，写清楚了，代码哪怕不优雅也能对。以后碰到再奇怪的排序题，都按这个节奏来：先加工键值，再定比较规则，最后输出原值。地基打稳了，后面盖楼才快。