P8686

Maysoul · 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;
}