蓝桥杯2024年第十五届决赛真题-兔子集结

解题思路:
将兔子分为两种(1.它和它的同伴相向而行  2.它和它的同伴不相向而行)。不难发现最后兔子的位置都位于第一种(它和它的同伴相向而行)兔子最后的位置上。所以我们可以首先确定第一种兔子的最终位置----(该兔子开始的位置+它同伴的开始位置)/2向下取整。然后在根据第一种兔子的位置确定第二种兔子的位置(该兔子移动方向上最先遇到的第一种兔子的位置)

举例：

                                 2  5  7  9  1

从小到大排序：         1  2  5  7  9

移动方向：                1 -1 1 -1 -1(-1表示往左，1表示往右)

确定第一种兔子位置：1  1  6  6  9

确定第二种兔子位置：1  1  6  6  6

还原：                        1  6  6  6  1

注意事项:

参考代码:

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

typedef struct
{
    long long l; // 位置
    long long n; // 编号
} Elem;

bool cmp(Elem a, Elem b)
{
    return a.l < b.l;
}

int main()
{
    long long N;
    cin >> N;
    vector<Elem> r(N);
    for (long long i = 0; i < N; i++)
    {
        cin >> r[i].l;
        r[i].n = i;
    }
    sort(r.begin(), r.end(), cmp);
    vector<long long> d(N);
    for (long long i = 1; i < N - 1; i++)
    {
        if (r[i].l - r[i - 1].l <= r[i + 1].l - r[i].l)
            d[i] = -1; // 表示左边的是他的同伴
        else
            d[i] = 1; // 右边
    }
    d[0] = 1;
    d[N - 1] = -1;
    vector<long long> loc(N);
    for (long long i = 0; i < N; i++)
        loc[i] = r[i].l;
    long long ok = 0;
    for (long long i = 0; i < N; i++)
        if (d[i] == 1 && d[i + 1] == -1) // 如果两个兔子相向而行
            loc[i] = loc[i + d[i]] = (loc[i] + loc[i + d[i]]) / 2;
    for (long long i = 0; i < N; i++)
    {
        if (!((d[i] == 1 && d[i + 1] == -1) || (d[i] == -1 && d[i - 1] == 1))) // 如果没有兔子与该相向而行
        {
            int k = i + d[i];
            while (!(d[k] == d[i] && d[k + d[i]] == -d[i])) // 找到合适的位置
                k = k + d[i];
            loc[i] = loc[k];
        }
        r[i].l = loc[i];
    }
    unordered_map<long long, long long> location;
    for (long long i = 0; i < N; i++)
        location[r[i].n] = loc[i];
    // 输出兔子位置
    for (long long i = 0; i < N; i++)
        cout << location[i] << " ";
    return 0;
}