B. Unconventional Pairs

问题描述

一个名为“非传统配对”的热门真人秀节目已在该市推出。根据节目规则，参与者以一种不寻常的方式配对：对于偶数人数，所有参与者都必须成对。

Petya 有一个包含 $n$ 个整数的数组 $a_1, a_2, \ldots, a_n$。已知 $n$ 是偶数。Petya 必须将参与者（数字）分成恰好 $\frac{n}{2}$ 对 $(a_{p_1}, a_{q_1}), (a_{p_2}, a_{q_2}), \ldots, (a_{p_{\frac{n}{2}}}, a_{q_{\frac{n}{2}}})$。每个索引最多只能包含在一对中。

对于一对 $(x, y)$，其差值定义为 $|x - y|$。Petya 希望组成非传统的配对，使得所有配对中的最大差值最小化。

确定这个最大差值的最小可能值。

题解

为了最小化所有配对中的最大差值，最好的策略是在对数组排序后，将相邻的元素配对。

首先，将数组 $a$ 按非递减顺序排序。设排序后的数组为 $a'_1, a'_2, \ldots, a'_n$。

最优的配对策略是形成配对 $(a'_1, a'_2), (a'_3, a'_4), \ldots, (a'_{n-1}, a'_n)$。对于每对 $(a'_{2i-1}, a'_{2i})$，其差值为 $a'_{2i} - a'_{2i-1}$，其中 $i = 1, \ldots, \frac{n}{2}$。

这些配对中的最大差值将是 $\max_{i=1}^{\frac{n}{2}} (a'_{2i} - a'_{2i-1})$。

这个策略是最优的，因为任何其他的配对都会涉及“跨越”元素，这将导致更大或相等的最大差值。例如，如果我们配对 $a'_i$ 和 $a'_k$ 以及 $a'_j$ 和 $a'_l$，其中 $i < j < k < l$，差值为 $a'_k - a'_i$ 和 $a'_l - a'_j$。而另一种配对 $(a'_i, a'_j)$ 和 $(a'_k, a'_l)$ 会得到更小的差值 $a'_j - a'_i$ 和 $a'_l - a'_k$。

因此，最大差值的最小可能值是排序后数组中成对相邻元素之间的最大差值。

提交链接