Dom And Parts :
Difficulty Level : Medium
Submissions : 520
Asked In :
Marks :10
: 5 | : 1
Dom is out to buy parts at his favourite garage. Each part has a strength value associated with it. As we know, while buying parts, one has to keep in mind the symmetry and stability of the car. For these reasons, Dom wants to buy the parts in pairs, and needs P (independent) pairs of parts for his car.
Also, whenever he buys a pair, there is an associated instability with it, which is defined as the absolute difference between the strength value of the parts , i.e - if he choses parts with strength 4 and 3, the instability is 1.
Help Dom buy P (independent) pairs from the N parts such that the effective instability is minimised.
The effective instability is the max instability of all pairs.
The first line contains T (1 <= T <= 1e5) - The number of test cases
First line of each test case contains N (2 <= N <= 1e5) and P (1 <= P <= N/2).
Second line contains N space separated integers, containing A[i] (1 <= A[i] <= 1e9) - the strength values of the parts.
Sum of N over all test cases does not exceed 1e5.
Single line containing single integer, the minimum effective stability.
3 5 2 1 2 3 4 5 10 3 1 5 6 2 4 5 1 10 9 59 10 4 1 5 6 2 4 5 1 10 9 59
1 1 1
In the first test case, we can take (1,2),(4,5) as the two pairs, instability will be 1,1 respectively, hence effective instability=1.
In the second test case, we can take (5,6),(4,5),(1,1) as the three pairs, instability will be 1,1,0 respectively, hence effective instability=1.
