CF1175C Electrification

最初，这道题的名字还有一个传说，但现在只剩下一个正式的题目描述。 给定 $n$ 个点 $a_1, a_2, \dots, a_n$，它们都在 $OX$ 轴上。现在请你找到一个整数点 $x$（也在 $OX$ 轴上），使得 $f_k(x)$ 的值尽可能小。 函数 $f_k(x)$ 的定义如下： - 先构造一个距离列表 $d_1, d_2, \dots, d_n$，其中 $d_i = |a_i - x|$（即 $a_i$ 与 $x$ 的距离）； - 将距离列表 $d$ 按非降序排序； - 取排序后第 $k+1$ 小的距离 $d_{k+1}$ 作为结果。 如果有多个最优解，你可以输出其中任意一个。

第一行包含一个整数 $T$（$1 \le T \le 2 \cdot 10^5$），表示询问的组数。接下来的 $2 \cdot T$ 行描述每组询问。所有询问相互独立。 每组询问的第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 2 \cdot 10^5$，$0 \le k < n$），分别表示点的数量和常数 $k$。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_1 < a_2 < \dots < a_n \le 10^9$），表示这些点，且已按升序排列。 保证所有询问中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出 $T$ 行，每行一个整数，表示对应每组询问中使 $f_k(x)$ 取得最小值的 $x$。如果有多个答案，可以输出任意一个。

由 ChatGPT 4.1 翻译