1. 从一道经典题看信息学竞赛的“第一道坎”如果你刚开始接触信息学奥赛OI或者正在刷《信息学奥赛一本通》这类经典教材那么“明明的随机数”这道题你大概率绕不过去。它在洛谷的编号是P1059在OpenJudge NOI 1.10里是第09题也是2006年NOIP普及组的真题。表面上看题目描述简单得让人放松警惕明明生成了一堆随机数你需要帮他“去重”并“排序”最后输出结果。很多新手尤其是刚学完数组和循环的同学一看就觉得“这太简单了”然后兴冲冲地写一个双重循环去重再来个冒泡排序提交后却可能只拿到部分分数甚至超时TLE。这道题之所以经典被各大OJ平台收录并作为《信息学奥赛一本通》等教材的例题正是因为它精准地卡在了“入门”与“入门后”的分界线上。它考察的绝不仅仅是你会不会写排序和去重的代码而是考察你能否跳出“模拟人工过程”的思维定式能否意识到数据结构和算法选择对程序效率的决定性影响。可以说顺利解决这道题意味着你的编程思维完成了从“实现功能”到“高效实现功能”的第一次跃迁。它就像一块试金石能清晰地区分出“仅会语法”的coder和“具备算法思维”的竞赛选手。2. 题目本质剖析去重排序的多种实现路径与效率陷阱我们先抛开具体的代码深入理解一下题目的核心要求。题目会给定一个正整数NN ≤ 100以及N个范围在1到1000之间的整数。我们需要完成两个任务第一去除其中重复的数字第二将剩余的唯一数字按从小到大的顺序输出。最后还需要输出去重后数字的个数。最直观、最符合人类思维的做法我称之为“暴力模拟法”。其步骤如下读入所有数字到一个数组。去重遍历数组对于每个元素再遍历它之后的所有元素如果找到相同的就将后面的元素“删除”通常用标记或者覆盖的方式。排序对去重后的数组片段使用简单的排序算法如冒泡排序或选择排序。输出。这个方法的代码逻辑直白对于N100这样的小数据量在功能上是完全正确的。但是它在效率上存在严重问题。去重操作的双重循环时间复杂度是O(N²)排序操作如果也用冒泡又是O(N²)。整体复杂度接近O(N²)。虽然对于N100现代计算机瞬间就能算完但这会养成一个非常不好的习惯不考虑算法复杂度。一旦题目数据范围扩大到N10⁵你的程序将毫无悬念地超时。那么正确的思维路径应该是怎样的我们应该将“去重”和“排序”这两个操作结合起来考虑甚至利用一些现成的“工具”来一站式解决。这里的关键在于题目给定的数字范围是有限的1-1000这个条件至关重要。它为我们打开了另一扇门桶排序Bucket Sort或称为计数排序Counting Sort的思想。我们可以创建一个大小为1001的布尔数组或整型数组初始值全部为false或0。这个数组的每一个位置下标就对应一个可能的数字1到1000。然后我们只需要读入数字并将数组中对应下标的位置标记为true或计数1。这个过程同时完成了“去重”因为同一个数字只会标记一次和“归类”。最后我们只需要从小到大遍历这个标记数组将所有值为true的下标输出即可输出的顺序自然就是升序。这种方法的时间复杂度是O(N M)其中N是输入数字个数M是数值范围这里是1000。它完全避免了比较性的排序效率极高且代码极其简洁。这就是算法思维带来的降维打击。3. 核心解决方案详解桶排序/计数排序的实战应用理解了“桶”的思想后我们来看具体的代码实现。这里以C为例因为这是信息学竞赛的主流语言。3.1 数据结构选择与初始化我们选择使用一个布尔型数组bool bucket[1001]。为什么是1001因为数字范围是1到1000数组下标从0开始为了能直接用数字作为下标访问bucket[数字]我们需要将数组大小定义为1001这样下标0-1000都有效我们只使用1-1000的部分。#include iostream using namespace std; int main() { int n, num; bool bucket[1001] {false}; // 初始化所有桶为false表示数字未出现 int count 0; // 用于统计去重后数字的个数 cin n; for (int i 0; i n; i) { cin num; bucket[num] true; // 将数字对应的桶标记为true } // ... 后续处理 }初始化时用{false}将整个数组置为false这是一个好习惯。count变量先准备好。3.2 读入与标记一举两得的去重读入循环是核心之一。注意bucket[num] true;这行代码。无论数字num出现多少次执行这行代码的效果都是一样的将bucket[num]设为true。这天然地实现了去重功能。第一次出现会标记后续再出现只是重复标记结果不变。3.3 遍历输出自动完成的排序读入并标记完成后我们只需要从1到1000遍历这个桶数组。// 首先统计有多少个true即不重复数字的个数 for (int i 1; i 1000; i) { if (bucket[i]) { count; } } cout count endl; // 然后按顺序输出这些数字 for (int i 1; i 1000; i) { if (bucket[i]) { cout i ; } } cout endl; // 最后换行这是一个好的输出习惯第一个循环统计个数第二个循环输出数字。因为我们是按下标从小到大遍历的所以输出的数字自然就是升序排列。整个过程没有调用任何排序函数却完美达成了排序和去重的目的。注意输出格式是这道题一个非常容易忽略的坑点。题目要求先输出去重后数字的个数然后换行再输出排序后的序列。序列中每个数字后面跟一个空格但最后一个数字后面是否允许有空格根据洛谷等OJ的判题规则通常“行末空格”是可以被接受的即忽略行尾多余空格但为了养成严谨的习惯我们可以选择在输出数字时进行判断如果是最后一个数字就不输出空格。不过对于本题直接在每个数字后输出空格最后输出一个换行是完全没有问题的通用写法。4. 方案对比与扩展当数据范围变大时怎么办桶排序法之所以在这道题上如此高效和简洁根本前提是数据范围很小且已知1-1000。这让我们可以开辟一个固定大小的数组来充当“桶”。如果题目条件变了呢我们有必要探讨其他通用性更强的解法这也是竞赛中更常见的场景。场景一数据范围很大例如1-10⁹但总数量N不大≤10⁵。这时开一个10⁹大小的数组完全不现实。我们应该采用“通用排序去重”策略。使用高效排序将N个数字读入数组直接使用C STL中的sort()函数进行排序时间复杂度为O(N log N)。在有序数组上去重排序后相同的数字会紧挨在一起。我们只需要遍历排序后的数组跳过重复的元素将不重复的元素收集到结果数组或者直接输出第一个然后遇到与上一个输出不同的再输出。这个过程是O(N)。#include iostream #include algorithm using namespace std; int main() { int n; cin n; int nums[n]; for (int i 0; i n; i) cin nums[i]; sort(nums, nums n); // 快速排序 int count 0; // 方法1直接输出通过比较相邻元素去重 cout nums[0] ; count 1; for (int i 1; i n; i) { if (nums[i] ! nums[i-1]) { cout nums[i] ; count; } } cout endl count endl; }场景二仅需去重不关心顺序。此时可以使用set集合数据结构。set的特性就是自动去重和排序内部通常是红黑树实现。代码会非常简洁#include iostream #include set using namespace std; int main() { int n, num; setint s; cin n; for (int i 0; i n; i) { cin num; s.insert(num); } cout s.size() endl; for (auto it s.begin(); it ! s.end(); it) { cout *it ; } cout endl; }set自动完成了所有工作但它的时间复杂度是O(N log N)且常数比直接排序要大一些。在竞赛中如果允许使用STL且对代码简洁度要求高set是一个不错的选择。但对于本题这种对性能要求极高的场景桶排序是更优解。场景三数据范围未知且可能包含负数。桶排序需要非负整数下标。如果包含负数我们需要进行偏移处理。例如数字范围是-1000~1000我们可以开一个大小为2001的数组访问时使用bucket[num 1000]将负数映射到正数下标。通过对比可以看出原题“明明的随机数”通过设定小的、固定的数据范围巧妙地引导竞赛新手去发现并应用桶排序这一非比较排序算法其教学意义远大于题目本身的功能实现。5. 在NOI Linux环境下编译与调试实战信息学竞赛的官方环境是NOI Linux这是一个基于Ubuntu的定制系统。掌握在这个环境下的开发流程是参赛的基本功。我们以本题的C代码为例。假设你的代码文件名为random.cpp。打开终端进入代码所在目录。编译使用g编译器。最基本的编译命令是g random.cpp -o random这条命令将random.cpp编译成名为random的可执行文件。-o参数用于指定输出文件名。进阶编译选项在竞赛中为了获得更好的性能和安全检查通常会加上一些优化和警告选项g random.cpp -o random -O2 -Wall -Wextra -stdc11-O2启用二级优化能显著提升程序运行速度这是竞赛中的标配。-Wall和-Wextra启用大部分警告信息帮助你在编码阶段发现潜在问题如未使用的变量、可疑的类型转换等。-stdc11指定使用C11标准。NOI系列赛事目前已支持C14但指定一个明确的标准是好习惯。运行与测试编译成功后生成random文件。运行它./random程序会等待输入。你可以手动输入题目样例进行测试。例如题目样例10 20 40 32 67 40 20 89 300 400 15输入后按回车程序会输出结果。你应该看到8 15 20 32 40 67 89 300 400输出个数8以及排序去重后的序列文件输入输出重定向手动输入很麻烦尤其是测试多组数据时。更常用的方法是使用输入输出重定向。将测试数据保存到一个文本文件例如in.txt。运行程序时让程序从in.txt读取输入并将输出保存到out.txt./random in.txt out.txt然后使用cat命令或文本编辑器查看out.txt的内容与标准答案对比。调试如果程序输出错误就需要调试。最朴素的调试方法是“打印调试法”printf/cout调试法在代码中关键位置插入输出语句查看变量中间值。对于更复杂的问题可能需要学习使用gdb命令行调试器但在入门阶段打印调试法足够有效。在NOI Linux中写代码推荐使用Code::Blocks、Geany或VSCode需自行安装等集成编辑器它们能提供语法高亮和基本的项目管理功能。但务必熟悉终端命令行的编译和运行操作因为比赛时最终的操作环境很可能就是纯命令行。6. 洛谷等OJ平台的提交策略与“坑点”规避在洛谷、OpenJudge等在线评测系统OJ上提交代码与本地运行略有不同。你需要将完整的源代码不含文件操作提交到网页上的代码框。针对本题的常见提交“坑点”数组大小这是最经典的错误。如果你用桶排序数组必须至少是bool bucket[1001]如果你声明成bucket[1000]那么当输入数字为1000时访问bucket[1000]就会发生“数组下标越界”可能导致运行时错误RE或得到错误结果。务必检查数组大小是否比数据最大值至少大1。变量未初始化局部变量如count如果不初始化它的值是随机的“垃圾值”。在有些评测环境下这可能初始化为0但在另一些环境下可能不是。这会导致结果不可预测。养成声明变量时立即初始化的好习惯例如int count 0;。输出格式前文已提到要严格按照题目要求输出。先输出个数并换行再输出序列。序列末尾的多余空格通常不影响判题但换行符endl一定要有。一个稳妥的写法是cout count endl; // 先输出个数并换行 bool first true; // 标记是否是第一个输出的数字 for (int i 1; i 1000; i) { if (bucket[i]) { if (!first) cout ; // 如果不是第一个先输出空格 cout i; first false; } } cout endl; // 序列输出完毕后再换行这样可以确保序列格式完全正确。时间复杂度与复杂度虽然本题数据小任何方法都能过。但如果你提交了一个O(N²)的冒泡排序去重解法在洛谷上也能通过。不过我强烈建议你使用桶排序法提交并思考其原理。在练习其他题目时一定要有复杂度意识先估算数据规模N的最大值再选择算法。使用STL的unique函数这是一种更“C”的写法。先sort再用unique函数将重复元素移到末尾并返回新结尾的迭代器最后输出。代码更简洁sort(nums, nums n); int new_len unique(nums, nums n) - nums; // 去重并得到新长度 cout new_len endl; for (int i 0; i new_len; i) cout nums[i] ;这种方法同样高效且是处理通用去重排序问题的标准写法之一值得掌握。在OJ上做题一次提交错误后要仔细阅读评测结果。常见的反馈有AC (Accepted)通过。WA (Wrong Answer)答案错误。检查逻辑、数组大小、初始化、输出格式。TLE (Time Limit Exceeded)超时。算法太慢必须优化。RE (Runtime Error)运行时错误。除零、数组越界、栈溢出等。CE (Compilation Error)编译错误。检查语法。对于本题只要理解了桶排序的思想注意了数组大小和输出格式一次AC应该是顺理成章的结果。这道题的价值就在于通过这个简单的入口让你亲身体验到“选择合适算法”带来的巨大差异这是通往更高阶算法学习必经的启蒙一课。