← 返回题目列表

Codeforces · 1360/B

B. 诚实的教练

中文机器翻译题面 查看原题

你面前有 $$$n$$$ 运动员。运动员从左到右编号为 $$$1$$$ 至 $$$n$$$。您知道每个运动员的实力 - 编号为 $$$i$$$ 的运动员的实力为 $$$s_i$$$。

您想要将所有运动员分成两队。每队必须至少有一名运动员,并且每位运动员必须恰好在一个队中。

您希望第一队中最强的运动员与第二队中最弱的运动员的差异尽可能小。正式而言,您希望将运动员分为 $$$A$$$ 和 $$$B$$$ 两队,以使值 $$$|\max(A) - \min(B)|$$$ 尽可能小,其中 $$$\max(A)$$$ 是 $$$A$$$ 队中运动员的最大力量,而 $$$\min(B)$$$ 是 $$$B$$$ 队中运动员的最小力量。

例如,如果 $$$n=5$$$ 且运动员的实力为 $$$s=[3, 1, 2, 6, 4]$$$,则可能的分组之一是:

- 第一队:$$$A = [1, 2, 4]$$$,
- 第二队:$$$B = [3, 6]$$$。

在这种情况下,值 $$$|\max(A) - \min(B)|$$$ 将等于 $$$|4-3|=1$$$。此示例说明了最佳分成两个团队的方法之一。

打印最小值 $$$|\max(A) - \min(B)|$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 输入中测试用例的数量。然后是 $$$t$$$ 测试用例。

每个测试用例由两行组成。

第一行包含正整数 $$$n$$$ ($$$2 \le n \le 50$$$) — 运动员人数。

第二行包含 $$$n$$$ 正整数 $$$s_1, s_2, \ldots, s_n$$$ ($$$1 \le s_i \le 1000$$$),其中 $$$s_i$$$ — 是第 $$$i$$$ 位运动员的力量。请注意,$$$s$$$ 值可能不不同。

输出

对于每个测试用例,打印一个整数 - $$$|\max(A) - \min(B)|$$$ 的最小值,并将所有运动员最佳分成两队。每位运动员必须是两支球队之一的成员。

示例

输入 #1

5
5
3 1 2 6 4
6
2 1 3 2 4 3
4
7 9 3 1
2
1 1000
3
100 150 200

输出 #1

1
0
2
999
50

注意

第一个测试用例在声明中进行了解释。在第二个测试用例中,最佳分割之一是 $$$A=[2, 1]$$$,$$$B=[3, 2, 4, 3]$$$,因此答案是 $$$|2-2|=0$$$。