问题 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。
输出
每组测试数据,输出一个整数,表示两组中位数之差的绝对值的最小值。
提示
在测试样例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。
来源
[提交][状态]