题意:给一数组,求原数组,给定的数组第i位表示原数组1到i的最大值。
输出可能的原数组的最小字典序和最大字典序。
最小字典序:第一次出现的ai即是当前点,那么其他的顺序从小到大写就完了。
最大字典序:类似并查集的路径优化
int a[N],ans1[N],ans2[N],mp[N],n; int find(int x){ if(mp[x]==x){ mp[x]=x-1; return x; } return mp[x]=find(mp[x]); } void solve(){ memset(ans1,0,sizeof(ans1)); memset(mp,0,sizeof(mp)); cin>>n; for(int i=1;i<=n;++i){ cin>>a[i]; if(mp[a[i]]==0){ mp[a[i]]=1; ans1[i]=a[i]; } } int pos=1; for(int i=1;i<=n;++i){ if(ans1[i]==0){ while(mp[pos]==1) pos++; mp[pos]=1; ans1[i]=pos; } } // for(int i=1;i<=n;++i) mp[i]=i; for(int i=1;i<=n;++i) ans2[i]=find(a[i]); for(int i=1;i<=n;++i) cout<<ans1[i]<<" "; cout<<endl; for(int i=1;i<=n;++i) cout<<ans2[i]<<" "; cout<<endl; }