A72012 | $蚂蚁相遇(ant)$

来源编程题

时间限制1s

内存限制512MB

通过 / 提交0/0

题目描述

有 n 只蚂蚁分布在数轴上，第 i 只蚂蚁初始位置为 x_i （保证 x_i 为奇数）。 任意时刻，每只蚂蚁会选择一只“与自己不在同一位置且距离最近”的蚂蚁作为目标并朝它移动； 若满足最近距离的蚂蚁不止一只，则选择其中位置最靠左的一只。 所有蚂蚁速度相同。 当两只（或多只）蚂蚁相遇后，会立即再次按上述规则重新选择目标并继续运动，直到所有蚂蚁最终相遇到同一个位置。 可以证明，所有蚂蚁一定会相遇。请你求出最终相遇位置。

第一行输入一个整数 n 。 第二行输入 n 个整数 x_1,x_2,...,x_n 。

输出一个整数，表示最终相遇位置。

输入 #1

3
1 5 9

输出 #1

输入 #2

4
-7 -1 3 11

输出 #2

样例解释 样例 1 中，最终相遇位置为最左与最右初始位置中点：(1+9)/2=5。 样例 2 中，最左位置为 -7，最右位置为 11，最终相遇位置为 (-7+11)/2=2。 数据范围 数据点编号数据范围特殊性质1n \leq 10, |x_i| \leq 10^2输入严格递增2n \leq 100, |x_i| \leq 10^4位置互不相同3n \leq 1000, |x_i| \leq 10^5等差数列4n \leq 5000, |x_i| \leq 10^6大量重复位置5n \leq 2 \times 10^4, |x_i| \leq 10^9无特殊性质6n \leq 5 \times 10^4, |x_i| \leq 10^9无特殊性质7n \leq 10^5, |x_i| \leq 10^9输入严格递减8n \leq 10^5, |x_i| \leq 10^9不同位置数量不超过209n \leq 2 \times 10^5, |x_i| \leq 10^9包含边界奇数值10n \leq 2 \times 10^5, |x_i| \leq 10^9无特殊性质保证：n \geq 2,且所有x_i均为奇数。

C++ 编辑器

输入

输出