/ Vijos / 题库 /

Wormhole

Wormhole

描述

一维的世界就是一个数轴。这个世界的狭小我们几乎无法想象。

在这个数轴上,有N个点。从左到右依次标记为点1到N。第i个点的坐标为Xi。经过漫长时间的物理变化和化学变化,这个一维世界中产生了一个高等智慧文明,而这N个点都成为了这个文明的一座城市。而点1则成为了这个文明的首都。

出于政治上和经济上的需要,首都不能和任何城市相距太远。所以政府决定在某两个城市耗巨资修建虫洞。一个修建了虫洞的城市可以瞬移到另一个修建了虫洞的城市,从而大大缩短了N个城市相互之间的距离。原先从任意城市i到城市j的路程等于它们的距离|Xi - Xj|,而现在若两个城市附近都有修建了虫洞的城市,则可以先从i移动到附近的虫洞瞬移到城市j附近的虫洞再移动到j。

政府希望在两个合适的城市修建虫洞,使得修建虫洞以后从点1移动到任意城市经过的最短路程的最大值尽量小。请你计算这个路程的最小值是多少。

输入包含多组数据。

格式

输入格式

第一行包括一个正整数T,表示有T组测试数据。接下来依次是T组测试数据。

每组测试数据的第一行包括一个整数N,表示有N个城市。第二行,N个递增的整数,依次表示N个城市的坐标。

输出格式

输出文件包括T行,每行一个整数,依次表示每组测试数据的答案。

样例1

样例输入1

2
3
0 1 21
5
0 100 101 102 103

样例输出1

1
2

限制

1s

提示

30%的数据满足:2 <= N <= 200.
60%的数据满足:2 <= N <= 2000.
100%的数据满足:2 <= N <= 200,000, 1 <= T <= 5, |Xi| <= 10^9.

来源

GDKOI 2009

信息

ID
1763
难度
6
分类
贪心 点击显示
标签
(无)
递交数
579
已通过
165
通过率
28%
被复制
3
上传者

相关

在下列训练计划中:

RP++分类题库

在下列比赛中:

NOIP2012模拟赛第三弹