[蓝桥杯][2019年第十届真题]修改数组(并查集)_给定一个长度为n的数组a = [a1, a2,…,an],数组中有可能有重复出现的整数。现在小

题目描述
给定一个长度为 N 的数组 A = [A1, A2, · · · AN ]，数组中有可能有重复出现 的整数。

现在小明要按以下方法将其修改为没有重复整数的数组。小明会依次修改 A2,A3,··· ,AN。

当修改 Ai 时，小明会检查 Ai 是否在 A1 ∼ Ai−1 中出现过。如果出现过，则 小明会给 Ai 加上 1 ;如果新的 Ai 仍在之前出现过，小明会持续给 Ai 加 1 ，直 到 Ai 没有在 A1 ∼ Ai−1 中出现过。

当 AN 也经过上述修改之后，显然 A 数组中就没有重复的整数了。 现在给定初始的 A 数组，请你计算出最终的 A 数组

输入
第一行包含一个整数 N。 第二行包含N个整数A1,A2,··· ,AN

输出
输出N个整数，依次是最终的A1,A2,··· ,AN。

样例输入
5
2 1 1 3 4
样例输出
2 1 3 4 5
思路：对于没有出现过的数字，这一位的答案就是这个数字了，但是下面再出现这个数字的时候，那就要是它的下一位或者再往后了。如果出现过这个数字，我们就将这个数所在集合中最大的数字（祖先）输出。我们处理完这一位的答案之后，就把这个数和它的下一位用并查集合并在一起。
代码如下：

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int maxx=1e5+100;
int f[maxx],ans[maxx];
int n;

inline void init()
{
	for(int i=0;i<maxx;i++) f[i]=i;
}
inline int getf(int u)
{
	return (u==f[u]?u:f[u]=getf(f[u]));
}
inline void merge(int u,int v)
{
	int t1=getf(u);
	int t2=getf(v);
	if(t1>t2) f[t2]=t1;
	else if(t1<t2) f[t1]=t2;
}
int main()
{
	scanf("%d",&n);
	init();
	int x;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&x);
		ans[i]=getf(x);
		merge(ans[i],ans[i]+1);
	}
	for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
	cout<<endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

努力加油a啊，(^o)/~