← 返回题目列表

Codeforces · 1440/B

B. 中位数总和

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

长度为 $$$n$$$ 的整数数组的中位数是其元素非递减排序中位于 $$$\lceil {\frac{n}{2}} \rceil$$$(向上舍入)位置的数字。职位编号从 $$$1$$$ 开始。例如,数组 $$$[2, 6, 4, 1, 3, 5]$$$ 的中位数等于 $$$3$$$。中位数还存在一些其他定义,但在本问题中,我们将使用所描述的定义。

给定两个整数 $$$n$$$ 和 $$$k$$$ 以及 $$$nk$$$ 整数的非递减数组。将所有数字分成 $$$k$$$ 大小为 $$$n$$$ 的数组,使得每个数字都属于一个数组。

您希望所有 $$$k$$$ 数组的中位数之和尽可能大。求这个最大可能的总和。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 100$$$) — 测试用例的数量。接下来的 $$$2t$$$ 行包含测试用例的描述。

每个测试用例描述的第一行包含两个整数 $$$n$$$, $$$k$$$ ($$$1 \leq n, k \leq 1000$$$)。

每个测试用例描述的第二行包含 $$$nk$$$ 整数 $$$a_1, a_2, \ldots, a_{nk}$$$ ($$$0 \leq a_i \leq 10^9$$$) — 给定数组。保证数组是非递减的:$$$a_1 \leq a_2 \leq \ldots \leq a_{nk}$$$。

保证所有测试用例的 $$$nk$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数 - 所有 $$$k$$$ 数组的中位数的最大可能总和。

示例

输入 #1

6
2 4
0 24 34 58 62 64 69 78
2 2
27 61 81 91
4 3
2 4 16 18 21 27 36 53 82 91 92 95
3 4
3 11 12 22 33 35 38 67 69 71 94 99
2 1
11 41
3 3
1 1 1 1 1 1 1 1 1

输出 #1

165
108
145
234
11
3

注意

第一个测试的所有测试用例可能划分为数组的示例:

测试用例 $$$1$$$:$$$[0, 24]、[34, 58]、[62, 64]、[69, 78]$$$。中位数为 $$$0、34、62、69$$$。他们的总和是$$$165$$$。

测试用例 $$$2$$$: $$$[27, 61], [81, 91]$$$。中位数是 $$$27, 81$$$。他们的总和是$$$108$$$。

测试用例 $$$3$$$:$$$[2, 91, 92, 95], [4, 36, 53, 82], [16, 18, 21, 27]$$$。中位数为 $$$91、36、18$$$。他们的总和是$$$145$$$。

测试用例 $$$4$$$:$$$[3, 33, 35],[11, 94, 99],[12, 38, 67],[22, 69, 71]$$$。中位数为 $$$33、94、38、69$$$。他们的总和是$$$234$$$。

测试用例 $$$5$$$: $$$[11, 41]$$$。中位数是$$$11$$$。唯一中位数的总和是 $$$11$$$。

测试用例 $$$6$$$:$$$[1, 1, 1], [1, 1, 1], [1, 1, 1]$$$。中位数为 $$$1, 1, 1$$$。他们的总和是$$$3$$$。