试题 历届试题 修改数组(并查集)

传送门

 

 题解:大意是依次遍历每个数，若该数之前出现过，需要一直加一直到得到一个没有出现过的数。

这里可以用并查集解决，每次遍历一个点，输出其祖先节点，并将其祖先节点的祖先设为该祖先节点加一(即下一个位置)

#include<bits/stdc++.h>
using namespace std;
int f[2000005];
int a[2000005];
int find(int x){
    if(x!=f[x]){
        f[x]=find(f[x]);
    }
    return f[x];
}
void init(){
    for(int i=1;i<=2000000;i++){
        f[i]=i;
    }
}
int main(){
    int n;scanf("%d",&n);
    init();
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=0;i<n;i++){
        int x=find(a[i]);
        cout<<x<<" ";
        f[x]=x+1;
    }
    return 0;
}