Dotcpp  >  编程题库  >  蓝桥杯2024年第十五届决赛真题-兔子集结
题目 3298:

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

时间限制: 2s 内存限制: 192MB 提交: 1071 解决: 43

题目描述

    在森林幽静的一隅,有一村落居住着 n 只兔子。

    某个月光皎洁的夜晚,这些兔子列成一队,准备开始一场集结跳跃活动。村落中的每只兔子都占据一个位置,对于第 i 只兔子,其位置为 pi 。我们称位置较小的为左边,位置较大的为右边。

    按照兔子村落的习俗,每只兔子都会选择距离自己最近的兔子作为同伴,并向同伴所在的方向进行跳跃。如果一只兔子左边和右边的兔子距离它一样近,那么它会选择左边的兔子作为同伴。

    兔子的每次跳跃,只能向左或向右移动一个单位距离。也就是说,如果一只兔子当前位于 x 的位置,那么它下一次跳跃后会到达 x − 1 或者 x + 1 的位置。

当两只相互靠近的兔子之间的距离为 1 时,左边的兔子会停在原地,而右边的兔子会跳到左边兔子的位置上,完成集结。

    兔子们会一直跳跃,直到与自己最初选择的同伴完成集结后停下。

    请问,当所有兔子都完成集结后,每只兔子都分别位于哪个位置上?

输入格式

输入的第一行包含一个整数 n,表示兔子的数量。

第二行包含 n 个整数 p1, p2, · · · , pn ,相邻整数之间使用一个空格分隔,表示每只兔子的初始位置。

输出格式

输出一行包含 n 个整数,表示每只兔子完成集结后的位置。

样例输入

5
2 5 7 9 1

样例输出

1 6 6 6 1

提示

【样例说明】   

 兔子 1 选择的同伴为兔子 5,兔子 5 选择的同伴为兔子 1。由于它们彼此间的距离为 1,因此兔子 5 会停在原地,而兔子 1 会跳到位置 1 上,与兔子 5完成集结。

    兔子 2 选择的同伴为兔子 3,兔子 4 选择的同伴也为兔子 3。对于兔子 3来说,兔子 2 和兔子 4 与它的距离相同,所以它会选择左边的兔子 2 作为同伴。兔子 2 会向右跳一个位置,兔子 3 会向左跳一个位置,兔子 4 会向左跳一个位置。此时,兔子 2 和兔子 3 均位于位置 6,完成集结(停止跳跃)。兔子 4会继续向左跳跃,直到跳到位置 6 后与兔子 3 完成集结。


【评测用例规模与约定】

    对于 40% 的评测用例,2 ≤ n ≤ 500,1 ≤ pi ≤ 105,p1, p2, · · · , pn 各不相同。

    对于所有评测用例,2 ≤ n ≤ 105,1 ≤ pi ≤ 109,p1, p2, · · · , pn 各不相同。

标签