1. 项目概述从“修改数组”到并查集实战最近在带学生准备信奥和蓝桥杯刷到一道经典题目——P8686 [蓝桥杯 2019 省 A] 修改数组。这道题乍一看是个简单的数组操作很多新手会不假思索地写个循环去查找和修改结果一提交大概率是超时。这正是蓝桥杯和信奥赛题的典型风格题目描述平易近人但数据规模暗藏杀机直接暴力求解必然碰壁。这道题的核心其实是考察选手对“高效查找下一个可用位置”这一抽象问题的建模与解决能力而并查集正是解决此类问题的“神兵利器”。今天我们就来彻底拆解这道题不仅讲清楚如何用C实现更要把背后的算法思想、优化技巧以及我在调试中踩过的坑毫无保留地分享给你。简单来说题目要求我们处理一个数组。对于输入的每一个数如果这个数之前没有在数组中出现过那么它就可以保持原值放入对应位置如果已经出现过了我们就必须把它修改为一个大于它且尚未出现过的最小正整数。最终输出修改后的整个数组。例如输入[1, 1, 2, 3]处理过程是第一个1直接放第二个1发现1已存在于是找到2未出现放2接着2已存在刚放的找到3未出现放3最后3也已存在找到4放4。输出[1, 2, 3, 4]。数据范围是N最大可达10^5数值Ai最大可达10^6。如果对于每个重复的数字都从它开始向后逐个扫描直到找到一个空位最坏时间复杂度是O(N^2)在10^5的数据量下肯定会超时。因此我们必须寻找一种能够快速“跳跃”到下一个可用位置的方法。2. 核心思路解析为什么并查集是正解2.1 暴力法的瓶颈与优化方向我们先来分析一下最直观的暴力解法为什么不行。假设我们用一个布尔数组visited[1000010]来标记某个数字是否已经出现过。对于每个输入的数字x如果visited[x]为false说明x没出现过直接采用x并标记visited[x] true。如果visited[x]为true说明x已存在。那么我们需要执行一个循环while(visited[x]) x;直到找到一个未被访问的x然后采用它并标记。这个算法的瓶颈就在第2步的while循环。考虑一个极端情况输入是[1, 1, 1, 1, ..., 1]共10^5个1。处理第一个1后visited[1]true。处理第二个1时需要扫描visited[2],visited[3]... 假设一直扫到visited[100001]才找到空位。处理第三个1时由于2已经被占用它需要从3开始扫描... 这样总的时间复杂度趋近于 O(N^2)无法通过。那么优化方向是什么关键在于当我们使用了一个位置x后如果下次再遇到x我们不应该再傻傻地从x1开始逐个扫描而应该“记住”x之后下一个可用的位置在哪里。换句话说我们需要一种数据结构能够将一系列连续被占用的位置“组织”起来并快速查询这个集合的“下一个”空闲位置。这听起来是不是很像“查找”和“合并”操作没错这就是并查集Union-Find Set的典型应用场景。2.2 并查集在此题中的巧妙映射并查集通常用于处理一些不相交集合的合并与查询问题。在这里我们可以进行一个天才的映射将每一个整数位置看作一个独立的节点。初始时每个节点的“父节点”都是自己表示每个位置都可用。当我们**使用占据**了某个位置x后我们就将节点x与节点x1合并到同一个集合中。这个操作的含义是x被用了那么下次再有人想用x时它应该直接去尝试x1所在集合的代表元即下一个可用位置。查找操作find(x)的含义是找到x所在集合的“下一个可用位置”。如果x未被使用find(x)返回x本身如果x已被使用且与后续位置合并find(x)会返回这个连续被占用区间末尾的下一个空闲位置。具体到本题流程读入一个数a。计算root find(a)。这个root就是a当前应该放置的值即大于等于a的最小未使用数。输出root。标记root已被使用执行union(root, root1)。这将root所在的集合和root1所在的集合合并确保下次查找root时会直接指向新的可用位置。这个算法的精妙之处在于它通过并查集的路径压缩使得每次查找的均摊时间复杂度接近常数级 O(α(n))其中 α(n) 是反阿克曼函数增长极其缓慢对于本题数据范围可以认为是常数时间。因此整体算法时间复杂度约为 O(N α(N))完全能够应对 10^5 的数据量。注意这里并查集“父节点”指针的方向设计是关键。我们让父节点指向“下一个可能可用的位置”这是一种“向右合并”的经典思路。也有另一种理解fa[i]表示当i被占用时下一个应该尝试的位置。初始化fa[i] i。当i被占用后设置fa[i] find(i1)。两种实现本质相通。3. 数据结构设计与实现细节3.1 并查集的大小与初始化数值 Ai 最大为 10^6但经过修改后输出的值最大可能是多少最坏情况是输入了 10^5 个 10^6那么最后一个数会被修改到 10^6 10^5 - 1。因此我们的并查集数组需要开得足够大。一个稳妥的做法是开到MAX_A MAX_N 5即大约 1000000 100000 5 1100005。我通常习惯开得更大一些比如const int MAX 2000010;避免边界问题。初始化非常简单遍历并查集数组fa令fa[i] i即可。#include iostream #include cstdio using namespace std; const int MAX 2000010; // 足够大的范围 int fa[MAX]; void init() { for (int i 0; i MAX; i) { fa[i] i; } }3.2 并查集的核心操作查找与合并并查集的两个核心操作是find和merge(或union但union是C关键字通常用merge或unite)。查找Find这里我们采用路径压缩优化。在查找根节点即下一个可用位置的同时将查找路径上的所有节点都直接指向根节点极大加速后续查找。int find(int x) { if (fa[x] ! x) { fa[x] find(fa[x]); // 路径压缩 } return fa[x]; }对于本题find(x)的语义就是找到x所属集合的代表元也就是x应当被修改成的那个值。合并Merge当我们使用了位置x后需要将x和x1所在的集合合并。合并时通常将较小的根合并到较大的根上或者反之对本题影响不大因为我们的目的是建立“x指向x1的根”这个关系。一个直观的实现是void merge(int x, int y) { int fx find(x); int fy find(y); if (fx ! fy) { fa[fx] fy; // 将x的根指向y的根 } }在本问题的语境下我们调用merge(root, root 1)。这意味着将root所在的集合挂到root1所在的集合之下。当下次再find(root)时由于路径压缩会直接找到root1的根即下一个可用位置。3.3 完整算法流程与代码框架将上述部分组合起来主程序的逻辑就非常清晰了。int main() { init(); // 初始化并查集 int n; scanf(%d, n); // 使用scanf/printf加速输入输出 for (int i 0; i n; i) { int a; scanf(%d, a); int root find(a); // 找到a应该放置的位置 printf(%d, root); if (i ! n - 1) printf( ); merge(root, root 1); // 标记root已被使用 } printf(\n); return 0; }4. 关键难点与边界情况处理4.1 路径压缩的必要性与效率如果不使用路径压缩并查集的find操作在最坏情况下会退化成链状时间复杂度为 O(N)那么总体算法又会退化到 O(N^2)。路径压缩是保证效率的关键。上面的递归写法fa[x] find(fa[x])是最简洁的实现。对于极端追求效率或者担心递归栈溢出的情况也可以使用迭代写法int find(int x) { int r x; while (fa[r] ! r) r fa[r]; // 找到根 // 路径压缩 int i x, j; while (i ! r) { j fa[i]; fa[i] r; i j; } return r; }对于本题的数据范围递归写法完全足够代码也更清晰。4.2 数组越界问题这是本题实现中的一个常见陷阱。当我们进行merge(root, root 1)时root1可能超过我们声明的数组大小MAX吗理论上根据前面的分析最大值约为 1,100,000我们开的MAX2,000,010是安全的。但在编程时一个良好的习惯是进行判断或者确保数组开得足够大。我个人的经验是对于这类问题直接将并查集数组大小开到2 * (最大输入值 最大数量)并加上一个余量比如MAX 2000010可以一劳永逸地避免越界访问带来的未定义行为。4.3 输入输出效率蓝桥杯等竞赛中当数据量达到 10^5 级别时使用cin和cout可能会比scanf和printf慢很多导致不必要的超时。因此在竞赛编程中养成使用scanf/printf或关闭流同步的习惯是很好的。使用scanf/printf。如果非要使用cin/cout可以在main函数开头加上ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);来关闭与C标准流的同步提升速度。但要注意一旦加了这句就不能再混用scanf/printf和cin/cout了。5. 代码实现与逐行分析下面给出一个完整、稳健且带有详细注释的AC代码。#include iostream #include cstdio using namespace std; // 定义足够大的并查集数组大小。最大数10^6最多10^5个数结果最大可能略大于两者之和。 const int MAX_N 100005; const int MAX_A 1000000; const int MAX MAX_A MAX_N 10; // 加上余量 int fa[MAX]; // 并查集数组 // 并查集查找函数带路径压缩 int find(int x) { // 如果x不是根fa[x] ! x则递归查找其根并压缩路径 if (fa[x] ! x) { fa[x] find(fa[x]); // 路径压缩将x的父节点直接设为根 } return fa[x]; } // 并查集合并函数将x所在集合与y所在集合合并 void merge(int x, int y) { int fx find(x); int fy find(y); if (fx ! fy) { fa[fx] fy; // 这里简单的将fx挂到fy下。对于本题合并方向影响不大。 } } int main() { // 初始化并查集每个元素的父节点都是自己 for (int i 0; i MAX; i) { fa[i] i; } int n; scanf(%d, n); // 读入数字个数 for (int i 0; i n; i) { int a; scanf(%d, a); // 读入当前数字 // 关键步骤找到a应该放置的位置即大于等于a的最小未使用数 int root find(a); // 输出结果 printf(%d, root); if (i ! n - 1) { printf( ); // 最后一个数后面不输出空格 } // 关键步骤标记root已被使用将其与root1合并 // 这意味着下次再查找root时会直接找到root1所在集合的根即下一个可用位置 merge(root, root 1); } printf(\n); // 输出换行 return 0; }逐行分析核心循环int root find(a);对于输入afind(a)操作会返回什么如果a从未被使用过那么fa[a] afind(a)返回a自身。如果a已经被使用过那么在之前某次操作中必然执行过merge(a, a1)假设当时a是那个root。此时fa[a]可能指向a1或更后面的数。find(a)通过路径压缩会一直追溯到当前这个连续被占用区间后面的第一个空闲位置即根节点并返回它。printf(%d, root);输出这个找到的可用位置。merge(root, root 1);这是算法的精髓。我们将root这个刚刚被使用的位置和root1这个位置所在的集合合并。注意root1可能已经被使用也可能未被使用。merge操作会将root所在的集合目前只有root吗不一定如果之前root-1被用过且合并过那root可能已经在一个集合里的根指向root1所在集合的根。这相当于建立了一个“跳转指针”以后任何查找原本属于root集合的元素包括root本身都会直接跳转到root1集合的根也就是下一个可用的位置。6. 调试技巧与常见问题排查6.1 如何验证算法的正确性对于算法题尤其是竞赛题不能光靠样例。自己构造一些有代表性的测试数据非常重要小数据常规测试[1, 1, 2, 3]-[1, 2, 3, 4]。边界测试输入全部相同的数[5, 5, 5, 5]-[5, 6, 7, 8]。输入连续的数[1, 2, 3, 4]-[1, 2, 3, 4]应无修改。输入打乱的数[3, 1, 4, 1, 5]-[3, 1, 4, 2, 5]。可以手动模拟。大数据压力测试思维模拟想象输入10^5个1你的算法是否能在短时间内理论上O(N)完成并查集实现可以暴力循环不行。6.2 常见错误与排查表错误现象可能原因解决方案输出错误部分结果不对1. 并查集find函数未进行路径压缩。2.merge后find的结果逻辑错误。3. 数组越界修改了非法内存导致数据错乱。1. 检查find函数确保有fa[x] find(fa[x])。2. 用小的测试数据如[1,1,1]单步调试观察fa数组变化。3. 检查MAX常量是否足够大确保root1不会越界。运行超时TLE1. 使用了未优化的暴力算法。2. 并查集find函数是朴素递归无压缩或形成了长链。3. 输入输出使用cin/cout且未关闭同步。1. 确认算法是否为并查集O(N α(N))。2. 确认find函数包含路径压缩。3. 换用scanf/printf或为cin/cout添加加速语句。运行时错误RE1. 数组越界访问最常见。2. 递归find函数栈溢出本题数据深度不大一般不会。1.重点检查增大MAX值至少为MAX_A MAX_N 10。2. 将递归find改为迭代版本。内存超限MLE并查集数组开得过大如int fa[10000000]。计算所需最大空间合理定义MAX。本题MAX2000010内存约 8MB安全。6.3 单步调试理解并查集状态对于算法新手理解并查集如何工作最好的方式就是手动模拟。以输入[1, 1, 2]为例初始fa[1]1, fa[2]2, fa[3]3...处理第一个1find(1)1输出1。merge(1,2)。此时fa[1]2。假设合并方向为fa[fx]fy即fa[1]2处理第二个1find(1)。因为fa[1]2,find(2)2所以路径压缩后fa[1]2返回root2输出2。merge(2,3)。此时fa[2]3。处理2find(2)。因为fa[2]3,find(3)3返回root3输出3。merge(3,4)。 最终输出[1, 2, 3]fa[1]2, fa[2]3, fa[3]4。可以看到并查集像一条“链”将已使用的数字串起来链的末端指向下一个空闲位置。7. 算法扩展与同类问题联想掌握了这道题的并查集解法你就掌握了一类问题的通解。这类问题的核心特征是需要维护一个集合支持“查询某元素所在集合的代表元”和“合并两个集合”的操作并且查询操作往往带有“寻找下一个可用位置”的语义。同类问题举例座位分配问题有N个人每个人想坐编号为Ai的座位如果被占就坐下一个空位。问最终座位分配情况。邮箱/用户名注册用户想注册一个心仪的用户名如果已被占用系统自动推荐下一个可用的如user1, user2...。后台需要快速查询和标记。内存分配中的“首次适应”算法寻找一块足够大的连续空闲内存也可以使用类似的思路进行优化。并查集的其它优化除了路径压缩还有“按秩合并”将深度小的树合并到深度大的树上可以进一步保证理论复杂度。但在本题中路径压缩已经足够高效按秩合并并非必需。最后关于编码环境无论是用Visual Studio、VSCode还是Dev-C核心都是把算法思路理清。在本地调试时多构造几组边缘数据确保程序健壮性。这道“修改数组”题从暴力到并查集的优化过程非常经典地体现了算法思维在解决问题中的决定性作用——不是所有问题都能靠蛮力解决选择合适的工具才能四两拨千斤。