​​​​​​蓝桥杯2019年第十届省赛真题-修改数组 - C语言网 (dotcpp.com)

要注意的地方是1 ≤ Ai ≤ 1000000，所以无论是并查集还是vis数组都要开1000000以上

两种方法

1.按照访问过v[x]多少次数，相应地加上那么多次数

#include<bits/stdc++.h>
using namespace std;
int vis[1000010];
int n,x;
int main()
{
    cin.tie(0);ios::sync_with_stdio(0);
    cin>>n;
    for(int i=0;i<n;++i){
        cin>>x;
       while(vis[x])
       {
           vis[x]++;
           x+=vis[x]-1;
       }
        vis[x]++;
        cout<<x<<" ";
    }

    return 0;
}

2.并查集+路径压缩

p[i]的意思是i的父亲

#include<bits/stdc++.h>
using namespace std;
int p[1000002];
int n,x;
int find(int i)
{
    if(i==p[i])return p[i];
    return p[i]=find(p[i]);
}

int main()
{
    cin.tie(0);ios::sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=1000000;++i){
    p[i]=i;
    }
    for(int i=1;i<=n;++i){
        cin>>x;
        x=find(x);
        p[x]=x+1;
        cout<<x<<" ";
    }
    return 0;
}