← 返回题目列表

Codeforces · 1175/C

C. 电气化

中文机器翻译题面 查看原题

起初有一个与问题名称相关的传说,但现在只是一个正式的陈述。

您在 $$$OX$$$ 轴上获得 $$$n$$$ 点 $$$a_1, a_2, \dots, a_n$$$。现在要求您在 $$$OX$$$ 轴上找到这样一个整数点 $$$x$$$ ,使得 $$$f_k(x)$$$ 是最小可能的。

函数 $$$f_k(x)$$$ 可以用以下方式描述:

- 形成距离列表 $$$d_1, d_2, \dots, d_n$$$ 其中 $$$d_i = |a_i - x|$$$ ($$$a_i$$$ 和 $$$x$$$ 之间的距离);
- 按非降序对列表 $$$d$$$ 进行排序;
- 将 $$$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$$$) — 按升序排列的点。

保证 $$$\sum{n}$$$ 不超过 $$$2 \cdot 10^5$$$。

输出

打印 $$$T$$$ 整数 - 对应点 $$$x$$$ 具有最小可能值 $$$f_k(x)$$$。如果有多个答案,您可以打印其中任何一个。

示例

输入 #1

3
3 2
1 2 5
2 1
1 1000000000
1 0
4

输出 #1

3
500000000
4