← 返回题目列表

Codeforces · 1300/B

B. 分配给班级

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

提醒:奇数个元素的数组 $$$[a_1, a_2, \dots, a_{2k+1}]$$$ 的中位数定义如下:设 $$$[b_1, b_2, \dots, b_{2k+1}]$$$ 为数组中按排序顺序的元素。那么这个数组的中位数等于$$$b_{k+1}$$$。

有 $$$2n$$$ 个学生,第 $$$i$$$ 个学生的技能级别为 $$$a_i$$$。不能保证所有技能水平都是不同的。

让我们将班级的技能水平定义为班级学生技能水平的中位数。

作为学校校长,您希望将每个学生分配到 $$$2$$$ 班级之一,以便每个班级的学生人数为奇数(不能被 $$$2$$$ 整除)。班级中的学生人数可以相同或不同,由您选择。每个学生都必须被分配到一个班级。在这些分区中,您需要选择一个类别的技能水平之间的绝对差异最小化的分区。

您可以实现的最小可能绝对差是多少?

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) - 学生人数减半。

每个测试用例的第二行包含 $$$2n$$$ 整数 $$$a_1, a_2, \dots, a_{2 n}$$$ ($$$1 \le a_i \le 10^9$$$) — 学生的技能水平。

保证所有测试用例的$$$n$$$总和不超过$$$10^5$$$。

输出

对于每个测试用例,输出一个整数,即两个奇数类别的技能水平之间的最小可能绝对差异。

示例

输入 #1

3
1
1 1
3
6 5 4 1 2 3
5
13 4 20 13 2 5 8 3 17 16

输出 #1

0
1
5

注意

在第一个测试中,只有一种方法来划分学生 - 每个班级一个。技能水平的绝对差异将为$$$|1 - 1| = 0$$$。

在第二次测试中,可能的划分之一是让第一班学生的技能水平为 $$$[6, 4, 2]$$$,这样第一班的技能水平将为 $$$4$$$,第二班的学生为 $$$[5, 1, 3]$$$,这样第二班的技能水平将为 $$$3$$$。绝对差值为 $$$|4 - 3| = 1$$$。

请注意,您不能进行 $$$[2, 3]$$$、$$$[6, 5, 4, 1]$$$ 或 $$$[]$$$、$$$[6, 5, 4, 1, 2, 3]$$$ 等分配,因为班级的学生人数为偶数。

$$$[2]$$$、$$$[1, 3, 4]$$$ 也不可能,因为技能为 $$$5$$$ 和 $$$6$$$ 的学生未分配到班级。

在第三次测试中,您可以按以下方式分配学生:$$$[3, 4, 13, 13, 20], [2, 5, 8, 16, 17]$$$ 或 $$$[3, 8, 17], [2, 4, 5, 13, 13, 16, 20]$$$。两种划分都给出了尽可能小的绝对差异。