[蓝桥杯 2019 省 A] 修改数组 ———并查集练习（大学复健）

本题拿到第一反应桶排序思想似乎可以水过，但是很明显出问题了。

#include <bits/stdc++.h>
using namespace std;

int N;

inline int kd(){
	int x=0,f=1;char ch=getchar();
	while(isdigit(ch)==false){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)==true){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
int tong[5000009];
int num[500009];
int main(){
	cin>>N;
	for(int i=1;i<=N;i++){
		num[i]=kd();
		if(tong[num[i]]==1){
			while(tong[num[i]]!=0){
				num[i]++;
			}
			tong[num[i]]++;
			printf("%d ",num[i]);
		}
		else{
			tong[num[i]]++;
			printf("%d ",num[i]);
		}
		//for(int j=1;j<=10;j++)cout<<tong[j]<<" ";cout<<endl;
	}
	return 0;
} 

在代码中有一个一步一步往前跳的步骤，非常耗时间，所以最后T的两个点是因为这个地方的复杂度过高

while(tong[num[i]]!=0){
	num[i]++;
}

那么考虑什么算法可以快速查找或者跳过呢？

很明显，倍增不行，链表不行（其实想一下和并查集差不多）

那么与这种优化相似的并查集的路径压缩非常适合这种情况捏！！！(^▽)

#include <bits/stdc++.h>
using namespace std;

int N;
int num[500009];
int fa[500009];
inline int kd(){
	int x=0,f=1;char ch=getchar();
	while(isdigit(ch)==false){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)==true){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}

int find_fa(int now){
	if(fa[now]==now)return now;
	return fa[now]=find_fa(fa[now]);
}

int main(){
	cin>>N;
	for(int i=1;i<=100005;i++)fa[i]=i;
	for(int i=1;i<=N;i++){
		num[i]=kd();
		num[i]=find_fa(num[i]);
		fa[num[i]]=find_fa(num[i]+1);
		//for(int j=1;j<=5;j++)cout<<fa[j]<<" ";cout<<endl;
	}
	for(int i=1;i<=N;i++)cout<<num[i]<<" "; 
	return 0;
}