lanqiao oj 185 修改数组

#include<iostream>
#include<cstring>
#include<algorithm>
 
using namespace std ;
const int N = 1e6 +10 ;
int n ;
int a[N] ;
int s[N] ;
int find(int x){
  if(x != s[x]) s[x] = find(s[x]) ;
  return s[x] ;
}
int main(){
  cin >> n ;
  for(int i = 1 ; i <= N ;i ++) s[i] = i ; //因为我们要求的并查集可能很大，所以初始化更多一点 
  for(int i = 1 ; i <= n ;i ++){
    int x ; cin >> x ; 
    int root = find(x) ;//我们先找到这个数的根节点，根节点就是现在这个数已经排到的第几个数 
    a[i] = root ;//我们把a[i]安排根节 
    s[root] = find(root + 1) ;//因为根节点已经用了，所以我们把当前根节点的根节点，指向下一个数的根节点 
  }
  for(int i = 1 ; i <= n ;i ++) cout << a[i] <<" " ;
  cout << endl ;
}