文章

修改数组(2019省赛)

修改数组1.png

1 直接模拟(超时)

#include<bits/stdc++.h>
using namespace std;
const long long int maxn=1e5+10;
long long int a[maxn];
map<long long int ,long long int>mp;
int main()
{
    long long int n,i;
    cin>>n;
    for(i=1;i<=n;i++) cin>>a[i];
    for(i=1;i<=n;i++){
        if(mp[a[i]]==0){
            mp[a[i]]=1;
        }else {
            while(mp[a[i]]==1){
                a[i]+=1;
            }
            mp[a[i]]=1;
        }
    }
    for(i=1;i<=n;i++){
        cout<<a[i]<<' ';
    }cout<<endl;
    return 0;
}

2 并查集 并查集+路径压缩(不太懂)

#include<bits/stdc++.h>
using namespace std;
const long long maxn=2e6+10;
long long int a[maxn];
long long int find(long long int x){
    if(a[x]!=x) return a[x]=find(a[x]);
    return a[x];
}
int main()
{
    long long int n,i,x;
    cin>>n;
    for(i=1;i<=maxn;i++) a[i]=i;
    for(i=1;i<=n;i++){
        cin>>x;
        x=find(x);
        cout<<x<<' ';
        a[x]=x+1;
    }
    cout<<endl;
    return 0;
}

原题链接

https://www.lanqiao.cn/problems/185/learning/)

License:  CC BY 4.0