蓝桥杯2019年第十届真题-修改数组-题解(C++代码)

#include <iostream>
using namespace std;
int main()
{
    //暴力破解 时间超限55%
//    int n;
//    cin>>n;
//    int p[n];
//    for(int i=0;i<n;i++){
//        cin>>p[i];
//        for(int j=0;j<i;j++){
//            if(p[i]==p[j]){
//                p[i]++;
//                j=-1;
//            }
//            if(j==i-1){
//                break;
//            }
//        }
//        cout<<p[i]<<" ";
//    }
    //使用类似于散列表的做法，在定义一个数组，用来存储被访问过的，时间超限18%
//    int v[1000099];
//    for(int i=0;i<1000099;i++){
//        v[i]=0;
//    }
//    int n;
//    cin>>n;
//    int *p=new int[n];
//    for(int i=0;i<n;i++){
//        cin>>p[i];
//        while(1){
//            if(v[p[i]]==1){//说明被访问过
//                p[i]++;
//            }else{//没有被访问过的，就赋予1
//                v[p[i]]=1;
//                break;
//            }
//        }
//        cout<<p[i]<<" ";
//    }
    //优化上面的算法
    int v[1000099];//存储每次访问的次数
    for(int i=0;i<1000099;i++){
        v[i]=0;
    }
    int n;
    cin>>n;
    int *p=new int[n];
    for(int i=0;i<n;i++){
        cin>>p[i];
        while(1){
            if(v[p[i]]!=0){//说明被访问过了，p[i]=他自身加上他访问过的次数，同时这个数的访问次数要+1
                v[p[i]]++;
                p[i]+=v[p[i]]-1;
            }else{//没有被访问过的，就自加1
                v[p[i]]++;
                break;
            }
        }
    }
    for(int i=0;i<n;i++){
        cout<<p[i]<<" ";
    }
    return 0;
}