【洛谷 P8686】[蓝桥杯 2019 省 A] 修改数组 题解（并查集+路径压缩）

[蓝桥杯 2019 省 A] 修改数组

题目描述

给定一个长度为 $N$ 的数组 $A=[A_1,A_2,\cdots A_N]$，数组中有可能有重复出现的整数。

现在小明要按以下方法将其修改为没有重复整数的数组。小明会依次修改 $A_2,A_3,\cdots ,A_N$。

当修改 $A_i$ 时，小明会检查 $A_i$ 是否在 $A_1$ ∼ $A_{i-1}$ 中出现过。如果出现过，则小明会给 $A_i$ 加上 $1$；如果新的 $A_i$ 仍在之前出现过，小明会持续给 $A_i$ 加 $1$，直到 $A_i$ 没有在 $A_1$ ∼ $A_{i-1}$ 中出现过。

当 $A_N$ 也经过上述修改之后，显然 $A$ 数组中就没有重复的整数了。

现在给定初始的 $A$ 数组，请你计算出最终的 $A$ 数组。

输入格式

第一行包含一个整数 $N$。

第二行包含 $N$ 个整数 $A_1,A_2,\cdots ,A_N$。

输出格式

输出 $N$ 个整数，依次是最终的 $A_1,A_2,\cdots ,A_N$。

样例 #1

样例输入 #1

5
2 1 1 3 4

样例输出 #1

2 1 3 4 5

提示

对于 $80\%$ 的评测用例，$1\le N\le 10000$。

对于所有评测用例，$1\le N\le 10^5$，$1\le A_i\le 10^6$。

蓝桥杯 2019 年省赛 A 组 H 题。

思路

首先，定义了一些常量和全局变量。其中，N 是数组的最大长度，n 是实际数组的长度，pre 是一个数组，用于存储并查集的父节点信息。

接着，定义了一个名为 root 的函数，用于查找并查集中元素的根节点。如果元素 x 的父节点就是自身，那么 x 就是根节点，返回 x。否则，递归查找元素 x 的父节点的根节点，并在查找过程中进行路径压缩，也就是将元素 x 的父节点直接设为其根节点，这样可以提高后续查找的效率。

在 main 函数中，首先初始化并查集，将每个元素的父节点设为自身。然后，读取实际数组的长度 n。接着，对数组中的每个元素，首先输出其根节点，然后将其根节点的父节点设为根节点的下一个元素，即将元素值修改为没有在之前出现过的最小整数。

注意

并查集要用路径压缩优化，否则部分测试点会报 TLE。root 函数在查找元素的祖先的同时，它会将沿途的所有元素的父节点都直接指向祖先。这样，下次查找这些元素的祖先时，就可以直接找到，无需再次遍历路径。

AC代码

#include <algorithm>
#include <iostream>
#define mp make_pair
#define AUTHOR "HEX9CF"
using namespace std;
using ll = long long;

const int N = 1e6 + 1e5;
const int INF = 0x3f3f3f3f;
const ll MOD = 1e9 + 7;

int n;
int pre[N];

int root(int x) { return (x == pre[x]) ? x : pre[x] = root(pre[x]); };

int main() {
	for (int i = 1; i <= N; i++) {
		pre[i] = i;
	}
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		int t;
		scanf("%d", &t);
		printf("%d ", root(t));
		pre[root(t)]++;
	}
	return 0;
}