CF1300B Assigning to Classes

提醒：数组 $[a_1, a_2, \dots, a_{2k+1}]$ 的中位数定义如下：设 $[b_1, b_2, \dots, b_{2k+1}]$ 为该数组按升序排列后的结果，则该数组的中位数为 $b_{k+1}$。 有 $2n$ 名学生，第 $i$ 名学生的能力值为 $a_i$。不保证所有能力值互不相同。 我们将一个班级的能力值定义为该班所有学生能力值的中位数。 作为校长，你希望将每位学生分配到两个班级中的某一个，使得每个班级的人数都是奇数（即不能被 $2$ 整除）。每个班级的人数可以相等，也可以不同，由你决定。每个学生必须且只能被分配到一个班级。在所有满足条件的分班方案中，你希望选择一个使得两个班级能力值的绝对差最小的方案。 你能得到的最小绝对差是多少？

每个测试点包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示学生人数的一半。 第二行包含 $2n$ 个整数 $a_1, a_2, \dots, a_{2n}$（$1 \le a_i \le 10^9$），表示每位学生的能力值。 保证所有测试用例中 $n$ 的总和不超过 $10^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]$。这两种分法都能得到最小的绝对差。 由 ChatGPT 4.1 翻译