4059. 蟹老板的梦幻传送门真的能让宅男走出家门吗

单点时限: 1.0 sec

内存限制: 256 MB

蟹老板梦幻庄园门口是一条很长很长的大街,大街上一共有 $n$ 户人家,位置分别为 $a_1, a_2, \dots, a_n$。

由于这条街实在是太长了,隔得远的人家就很少串门。蟹老板为了方便大家沟通邻里感情,打算在大街上设置一对传送门,传送门是可以双向传送的,大街上的居民可以直接通过其中一个传送门瞬间转移到另一个传送门。所以蟹老板想问问你,怎样确定两个传送门的位置,可以使得距离最远的两户人家间的最短路径尽可能地短。传送门可以设置在任何坐标为实数的位置上。

换言之,令 $d(i,j)$ 表示建立传送门后,从第 $i$ 户人家到 $j$ 户人家的最短路径长度。则你需要确定两个传送门的位置使得 $\max_{i,j\in {1,2,\dots,n}} d(i,j)$尽可能地小,输出这个最小值。

输入格式

第一行,一个正整数 $n$($2 \le n \le 10^6$),表示街上的户口数。

接下来一行,共 $n$ 个正整数 $a_i$($1 \le a_i \le 10^9$),表示每户人家的位置。

输出格式

一行,一个整数,表示添加传送门后,距离最远的两户人家间的距离。可以证明,在最优策略下,答案一定为整数。

样例

Input
6
1 2 5 9 10 11
Output
4

提示

在 $3$ 和 $10$ 位置上设置一对传送门,那么离得最远的两户人家是第一户和第三户,位置分别是 $1$ 和 $5$,路径最短的走法是不经过传送门直接走,路径长度为 $4$。此时,原本离得最远的第一户人家和第六户人家,借助于传送门,二者距离仅有 $3$。

54 人解决,78 人已尝试。

60 份提交通过,共有 301 份提交。

4.5 EMB 奖励。

创建: 10 月,1 周前.

修改: 7 月,1 周前.

最后提交: 1 月,2 周前.

来源: EOJ Monthly 2021.3

题目标签