题解：P10577 [蓝桥杯 2024 国 A] 兔子集结

### 题意
给你 $N$ 只兔子，每只兔子会跟随离它最近的一只兔子。注意，如果这只兔子与另外两只兔子都相同，则**它会跟随左边的兔子**。当兔子与跟随的兔子距离差为 $1$，它们就会在更左边的兔子的位置相遇。最后询问每只兔子的最终位置。
### 思路
使用并查集。

我们使用一个数组 $b$ 记录值和位置，并根据值进行排序。  
我们知道跟随关系只有 $2$ 种

- 如果 $b_i$ 跟随 $b_{i+1}$，且 $b_{i+1}$ 跟随 $b_i$，它们就会在 $\frac {b_i+b_{i+1}} 2$ 处相遇。
- 如果 $b_i$ 跟随 $b_{i+1}$，且 $b_{i+1}$ 跟随 $b_{i+2}$，就将这些数并入一个集，当找到上一种跟随关系时，将这个集的值设为那两只兔子相遇的地方。

所以之后进行循环遍历，在循环里面确定跟随关系并计算每个集值，之后直接输出答案就行了。
### code
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,a[100002],ans[100002],ans1[100002],vis[100002];
struct father
{
	int fa,sum;
}fa[100002];
father fid(int x)
{
	if(fa[x].fa!=x) fa[x]=fid(fa[x].fa);
	return fa[x];
}
void rzgz(int x,int y)
{
	father aa=fid(x),bb=fid(y);
	if(aa.fa!=bb.fa) fa[bb.fa].fa=aa.fa;
	else fa[aa.fa].sum=(a[x]+a[y])/2;
}
struct s
{
	int sum,id;
}b[100002];
bool cmp(s x,s y)
{
	return x.sum<y.sum;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		b[i].sum=a[i];
		b[i].id=i;
		fa[i].fa=i;
	}
	sort(b+1,b+n+1,cmp);
	for(int i=1;i<=n;i++)
	{
		if(i==1) rzgz(b[i+1].id,b[i].id);
		else if(i==n) rzgz(b[i-1].id,b[i].id);
		else if(abs(b[i-1].sum-b[i].sum)>abs(b[i+1].sum-b[i].sum)) rzgz(b[i+1].id,b[i].id);
		else rzgz(b[i-1].id,b[i].id);
	}
	for(int i=1;i<=n;i++)
		cout<<fid(i).sum<<" ";
	return 0;
}
```

正在渲染内容...