自动搬运

查看原文

来自洛谷，原作者为

	Moonlight_dreams “那你就不要哭了，女孩子要笑才好看嘛…” || ”风是他对抗敌人的武器，但在她这里是抚平眼泪的爱意…“|| 粉蝶落金铃，蝶死金铃碎… || 本人是喜美圈的西梅汁~~ || ʕ̢̣̣̣̣̩·͡˔·ོɁ̡̣̣

搬运于2025-08-24 22:59:20，当前版本为作者最后更新于2025-04-22 17:34:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目

代码思路

• 排序

  我们可以用结构体，结构体里面有两个变量，一个是位置，一个是原来的序号。我们可以按照兔子的位置排序。

• 并查集

  初始化并查集，范围是 $1$ 到 $n - 1$。

• 找答案

  遍历整个数组，找到相邻的且方向不同的兔子，根据题意，我们令左兔子的位置为 $l$，右兔子的位置为 $r$，我们可以知道他们完成集结的位置是 $\frac{l + r}{2}$ 并且向下取整。

• 找答案

  最后我们再次遍历，找到答案。

AC 代码如下

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int fa[N];
struct stu
{
	int pos , id;
}s[N];
int get(int x)
{
	if(fa[x]==x)
		return x;
	return fa[x]=get(fa[x]);
}
bool cmp1(stu x , stu y)
{
	return x.pos < y.pos;
}
bool cmp2(stu x , stu y)
{
	return x.id < y.id;
}
signed main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> s[i].pos;
		s[i].id = i;
	}
	sort(s + 1 , s + n + 1 , cmp1);
	fa[1] = 2;
	fa[n] = n - 1;
	for (int i = 2; i <= n - 1; i++)
	{
		int lp = s[i - 1].pos , p = s[i].pos , rp = s[i + 1].pos;
		if (p - lp <= rp - p)
		{
			fa[i] = i - 1;
		}
		else
		{
			fa[i] = i + 1;
		}
	}
	for (int i = 1; i <= n - 1; i++)
	{
		if (fa[i] == i + 1 && fa[i + 1] == i)
		{
			fa[i] = i;
			fa[i + 1] = i + 1;
			int p = (s[i].pos + s[i + 1].pos) / 2;
			s[i].pos = s[i + 1].pos = p;
		}
	}
	for (int i = 1; i <= n; i++)
	{
		if (fa[i] != i)
		{
			int root = get(i);
			s[i].pos = s[root].pos;
		}
	}
	sort(s + 1 , s + n + 1 , cmp2);
	for (int i = 1; i <= n; i++)
	{
		cout << s[i].pos << " ";
	}
	return 0;
}