问题 5914 -- 兔兔的中位数

5914: 兔兔的中位数★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 20  解决: 11
[提交][状态][命题人:]

题目描述

给定一个长度为2n的数列{ai},现在需要把它分成两组,使得每一组的数量均为奇数。现在请你帮助计算出两组中位数之差的最小绝对值。

输入

第一行,一个整数t(t≤10000),代表数据组数。
每组数据包含两行。第一行,一个整数n (1≤n≤100000),表示数列长度的一半。第二行为2n个整数a1,a2,...a2n (1≤ai≤1e9)。
测试数据保证所有的n之和不超过100000。

输出

每组测试数据,输出一个整数,表示两组中位数之差的绝对值的最小值。
样例输入
Copy
3
1
1 1
3
6 5 4 1 2 3
5
13 4 20 13 2 5 8 3 17 16
样例输出
Copy
0
1
5

提示

在测试样例1中,只有一种分法,即每组一个整数。因此,中位数之差的绝对值为|1−1|=0。
在测试样例2中,一种可行的分组为: [6,4,2]与[5,1,3],中位数分别为4和3。因此,中位数之差的绝对值为|4−3|=1。注意,不能分为 [2,3]与[6,5,4,1]或[]与[6,5,4,1,2,3],因为这两种分法中的长度都不是奇数;也不能分为[2]与[1,3,4],因为5、6没分到相应的组中。
在测试样例3中,可行的分组为:[3,4,13,13,20]与[2,5,8,16,17]或[3,8,17]与[2,4,5,13,13,16,20],这两种分法中,中位数之差的绝对值都为5。

来源

 

[提交][状态]