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

Moonlight_dreams · 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;
}