自动搬运

查看原文

来自洛谷，原作者为

	Maysoul AFO(2023/3/15——2023/11/19)

搬运于2025-08-24 22:41:28，当前版本为作者最后更新于2023-05-02 16:16:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这道题可以采用并查集的方法来做。

先理清一下题意，我们需要将一个有重复整数的数组变为无重复整数的数组。对于 $A$ 中的一个数据 $a_{i}$，我们先看一下在 $a_{i}$ 的前面是否有 $a_{i-j}$ 与之相等，如果有 $a_{i-1}$ 的话，那就让 $a_{i}$ 加一，再重复上述操作。

当前面没有 $a_{i}$ 的时候，输出就是它本身，可是如果有呢？

我们可以设置一个并查集，在每次出现 $a_{i}$ 的时候，就把 $a_{i}$ 的父亲加一，由于一开始所有 $a_{i}$ 的父亲都是 $a_{i}$，所以可以保证其下一次再出现 $a_{i}$ 的时候发生变换，这也是并查集思想的直观体现。

AC CODE:

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+10;
int num,ans;
int fa[100100];
int find(int x)//并查集中的查询操作
{
	if(x==fa[x]) return x;
	return fa[x]=find(fa[x]);
}
int main()
{
	int n;
	cin>>n;
	for (int i=1;i<100100;i++)//所有数最开始都应指向它本身
	{
		fa[i]=i;
	}
	int a;
	for (int i=1;i<=n;i++)
	{
		cin>>a;
		a=find(a);//查询这个数
		fa[a]=find(a)+1;//修改它的父节点
		cout<<a<<" ";
	}
	return 0;
}