6124 - 蚂蚁相遇(ant)
题目描述
有 n 只蚂蚁分布在数轴上，第 i 只蚂蚁初始位置为 x_i（保证 x_i 为奇数）。
任意时刻，每只蚂蚁会选择一只“与自己不在同一位置且距离最近”的蚂蚁作为目标并朝它移动； 若满足最近距离的蚂蚁不止一只，则选择其中位置最靠左的一只。
所有蚂蚁速度相同。
当两只（或多只）蚂蚁相遇后，会立即再次按上述规则重新选择目标并继续运动，直到所有蚂蚁最终相遇到同一个位置。
可以证明，所有蚂蚁一定会相遇。请你求出最终相遇位置。
输入
第一行输入一个整数 n。
第二行输入 n 个整数 x_1,x_2,...,x_n。
输出
输出一个整数，表示最终相遇位置。
样例
输入
3 1 5 9
输出
5
输入
4 -7 -1 3 11
输出
2
说明
样例解释
样例 1 中，最终相遇位置为最左与最右初始位置中点：(1+9)/2=5。
样例 2 中，最左位置为 -7，最右位置为 11，最终相遇位置为 (-7+11)/2=2。
数据范围
| 数据点编号 | 数据范围 | 特殊性质 |
|---|---|---|
| 1 | n \leq 10, |x_i| \leq 10^2 | 输入严格递增 |
| 2 | n \leq 100, |x_i| \leq 10^4 | 位置互不相同 |
| 3 | n \leq 1000, |x_i| \leq 10^5 | 等差数列 |
| 4 | n \leq 5000, |x_i| \leq 10^6 | 大量重复位置 |
| 5 | n \leq 2 \times 10^4, |x_i| \leq 10^9 | 无特殊性质 |
| 6 | n \leq 5 \times 10^4, |x_i| \leq 10^9 | 无特殊性质 |
| 7 | n \leq 10^5, |x_i| \leq 10^9 | 输入严格递减 |
| 8 | n \leq 10^5, |x_i| \leq 10^9 | 不同位置数量不超过20 |
| 9 | n \leq 2 \times 10^5, |x_i| \leq 10^9 | 包含边界奇数值 |
| 10 | n \leq 2 \times 10^5, |x_i| \leq 10^9 | 无特殊性质 |
保证：n \geq 2,且所有x_i均为奇数。
来源
2026年常州“信息与未来”小学生编程比赛线上
标签
