信息学奥赛刷题实战：OpenJudge NOI 1.11 08题，手把手教你用C++ STL的set容器去重排序

信息学奥赛刷题实战用C STL的set容器优雅解决去重排序问题在信息学奥赛的备战过程中我们经常会遇到需要处理大量数据并去重排序的场景。传统的手写排序和查找算法虽然能解决问题但往往需要编写大量代码容易出错且效率不高。本文将带你探索C标准模板库(STL)中set容器的强大功能它能让你用更简洁、更优雅的方式解决这类问题。1. 为什么选择STL容器而非手写算法很多初学者在解决不重复输出这类问题时第一反应是手写排序和查找算法。这种思路固然正确但在竞赛环境下我们需要考虑更多因素开发效率手写二分查找和插入排序需要约50行代码而使用set容器只需不到20行维护成本手写算法更容易出现边界条件错误调试耗时执行效率set容器底层通常采用红黑树实现保证O(log n)的查找和插入复杂度代码可读性使用标准库能让代码意图更清晰便于他人理解// 传统手写算法示例部分代码 bool isFound(int x) { int l 1, r an, m; while(l r) { m (l r) / 2; if(x a[m]) r m - 1; else if(x a[m]) l m 1; else return true; } return false; }相比之下set容器的使用简直是一种享受// 使用set容器的等效功能 setint unique_numbers; unique_numbers.insert(x); // 自动去重和排序2. set容器核心特性与底层原理set是C STL中的关联式容器它为我们提供了开箱即用的去重和排序功能。理解其工作原理能帮助我们在不同场景下做出更明智的选择。2.1 set的核心特性自动去重相同的元素不会被重复存储自动排序元素默认按升序排列快速查找基于红黑树实现查找复杂度O(log n)动态大小不需要预先指定容量2.2 底层数据结构红黑树set通常基于红黑树一种自平衡二叉查找树实现这保证了即使在最坏情况下插入、删除和查找操作的时间复杂度都是O(log n)。红黑树通过以下规则保持平衡每个节点非红即黑根节点是黑色红色节点的子节点必须是黑色从任一节点到其每个叶子的所有路径包含相同数目的黑色节点提示虽然不需要手动实现红黑树但了解这些特性有助于理解set的性能特点。3. 实战用set解决OpenJudge NOI 1.11 08题让我们回到OpenJudge NOI 1.11 08题的具体问题输入n个数要求不重复地按升序输出这些数。以下是使用set容器的完整解决方案#include iostream #include set using namespace std; int main() { int n, x; cin n; setint unique_numbers; for(int i 0; i n; i) { cin x; unique_numbers.insert(x); } for(int num : unique_numbers) { cout num ; } return 0; }这个解决方案的优雅之处在于去重set自动处理重复值排序元素自动按升序排列简洁核心逻辑仅需3行代码高效整体时间复杂度O(n log n)3.1 性能对比让我们比较不同方法在处理10^5个随机整数时的表现方法代码行数时间复杂度内存使用实现难度手写插入排序二分查找~50O(n²)低高手写快速排序遍历去重~40O(n log n)低中STL sort遍历去重~20O(n log n)低低STL set~15O(n log n)中极低从表中可以看出set在实现难度和代码简洁性上有明显优势虽然内存使用略高但在大多数竞赛场景中是可接受的。4. 进阶技巧与最佳实践掌握了set的基本用法后让我们深入探讨一些能让你在竞赛中更高效使用set的技巧。4.1 自定义排序规则有时我们需要降序排列或按特定规则排序。set允许我们通过自定义比较函数来实现struct Descending { bool operator()(int a, int b) const { return a b; } }; setint, Descending descending_set;4.2 高效查找操作set提供了多种查找方法合理使用可以提升代码效率setint s {1, 3, 5, 7, 9}; // 检查元素是否存在 if(s.count(5)) { // 存在 } // 查找元素返回迭代器 auto it s.find(5); if(it ! s.end()) { // 找到元素 } // 查找第一个不小于给定值的元素 auto lower s.lower_bound(4); // 返回指向5的迭代器4.3 与其他容器的配合使用在实际问题中我们经常需要将set与其他容器配合使用vectorint input {3, 1, 4, 1, 5, 9, 2, 6, 5}; setint unique_sorted(input.begin(), input.end()); // 将结果转存到vector vectorint output(unique_sorted.begin(), unique_sorted.end());4.4 内存优化unordered_set的选择当只需要去重而不需要排序时可以考虑使用unordered_set它基于哈希表实现插入和查找的平均时间复杂度为O(1)#include unordered_set unordered_setint unique_numbers;但要注意unordered_set不保证元素顺序且在最坏情况下时间复杂度会退化到O(n)。5. 常见问题与调试技巧即使是经验丰富的选手在使用set时也可能遇到一些问题。以下是几个常见场景及其解决方案。5.1 迭代器失效问题在遍历set时修改容器会导致未定义行为setint s {1, 2, 3, 4, 5}; // 错误示范在遍历时删除元素 for(auto it s.begin(); it ! s.end(); it) { if(*it % 2 0) { s.erase(it); // 危险迭代器失效 } } // 正确做法 for(auto it s.begin(); it ! s.end(); ) { if(*it % 2 0) { it s.erase(it); // erase返回下一个有效迭代器 } else { it; } }5.2 自定义类型的set使用如果要存储自定义类型需要提供比较函数struct Point { int x, y; }; struct PointCompare { bool operator()(const Point a, const Point b) const { return a.x b.x || (a.x b.x a.y b.y); } }; setPoint, PointCompare point_set;5.3 性能调优当处理超大规模数据时可以考虑以下优化预先调用reserve()对于unordered_set使用emplace()而非insert()避免临时对象构造考虑内存局部性有时vectorsortunique可能更快vectorint v {3, 1, 4, 1, 5, 9, 2, 6, 5}; sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());在实际比赛中我通常会准备两种解决方案的模板根据题目数据规模选择最合适的实现方式。对于大多数中等规模数据(10^4-10^5)set是最省心的选择而对于超大规模数据(10^6)可能需要考虑更优化的方案。