2 1 3 4 5
首先就想到了常规的bool数组，循环+1的方法，然后超时了，得到分数为80。
所以就用了一个数据结构——并查集。
在计算机科学中，并查集是一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题。
在这个问题里，我们只要实现查找功能就好了。
AC代码并不复杂。如下：
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 //并查集 5 int f[1000001]; 6 int getf(int x) { 7 if (x == f[x]) 8 return x; 9 return f[x] = f[getf(f[x])]; 10 } 11 12 int main() { 13 for (int i=1;i<1000001;i++) 14 f[i] = i; 15 int n, t; 16 cin >> n; 17 while (n--){ 18 cin >> t; 19 t = getf(t); 20 cout << t; 21 f[t] = getf(t + 1); 22 if (n >= 1)cout << " "; 23 } 24 }
原文：https://www.cnblogs.com/zyyz1126/p/12372124.html