题目描述

You are building advanced chips for machines. Making the chips is easy, but the power supply turns out to be an issue since the available batteries have varied power outputs.

Consider the problem of $n$ machines, each with two chips, where each chip is powered by $k$ batteries. Surprisingly, it does not matter how much power each chip gets, but a machine works best when its two chips have power outputs as close as possible. The power output of a chip is simply the smallest power output of its $k$ batteries.

You have a stockpile of 2nk batteries that you want to assign to the chips. It might not be possible to allocate the batteries so that in every machine both chips have equal power outputs, but you want to allocate them so that the differences are as small as possible. To be precise, you want to tell your customers that in all machines the difference of power outputs of the two chips is at most $d$, and you want to make $d$ as small as possible. To do this you must determine an optimal allocation of the batteries to the machines.

Consider Sample Input $1$. There are $2$ machines, each requiring $3$ batteries per chip, and a supply of batteries with power outputs $1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12$. You can, for instance, assign the batteries with power outputs $1, 3, 5$ to one chip, those with power $2, 4, 12$ to the other chip of the same machine, those with power $6, 8, 9$ to the third chip, and those with power $7, 10, 11$ to the fourth. The power outputs of the chips are $1, 2, 6,$ and $7$, respectively, and the difference between power outputs is $1$ in both machines. Note that there are many other ways to achieve this result.

输入格式

The input consists of a single test case. A test case consists of two lines. The first line contains two positive integers: the number of machines $n$ and the number of batteries per chip $k (2nk \leq 10^6)$. The second line contains $2nk$ integers $p_i$ specifying the power outputs of the batteries $(1 \leq p_i \leq 10^9)$.

输出格式

Display the smallest number $d$ such that you can allocate the batteries so that the difference of power outputs of the two chips in each machine is at most $d$.

题目大意

【题目描述】

你正在为机器制造先进的芯片。制造芯片很容易，但电源供应却成为了一个问题，因为现有电池的输出功率各不相同。

考虑 $n$ 台机器的问题，每台机器有两个芯片，每个芯片由 $k$ 块电池供电。出人意料的是，每个芯片获得的电量多少并不重要，但机器在两个芯片的功率输出尽可能接近时工作效果最佳。芯片的功率输出仅为其 $k$ 块电池中输出功率最小的那块电池的输出。

你有一堆共 $2nk$ 块电池，你需要将它们分配给这些芯片。可能无法分配这些电池使得每台机器的两个芯片的功率输出都相等，但你希望尽量减小它们之间的差异。具体来说，你希望告诉客户，所有机器中两个芯片的功率输出差异至多为 $d$，并且你希望使 $d$ 尽可能小。为此，你必须确定电池分配给机器的最优方案。

考虑样例输入 $1$。有 $2$ 台机器，每个芯片需要 $3$ 块电池，有一组功率输出为 $1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12$ 的电池。你可以例如将输出功率为 $1, 3, 5$ 的电池分配给一个芯片，将输出功率为 $2, 4, 12$ 的电池分配给同一机器的另一个芯片，将输出功率为 $6, 8, 9$ 的电池分配给第三个芯片，将输出功率为 $7, 10, 11$ 的电池分配给第四个芯片。芯片的功率输出分别为 $1, 2, 6, 7$，两台机器中功率输出的差异分别为 $1$。注意，还有许多其他方式可以实现这一结果。

【输入格式】

输入包含一个测试用例。测试用例包含两行。第一行包含两个正整数：机器的数量 $n$ 和每个芯片所需的电池数 $k$ $(2nk \leq 10^6)$。第二行包含 $2nk$ 个整数 $p_i$，指定电池的功率输出 $(1 \leq p_i \leq 10^9)$。

【输出格式】

输出一个最小的数字 $d$，使你可以分配这些电池，使每台机器中两个芯片的功率输出差异至多为 $d$。

翻译来自于：ChatGPT。

2 3
1 2 3 4 5 6 7 8 9 10 11 12

1

2 2
3 1 3 3 3 3 3 3

2