A13946. Sum of Medians
编程题
普及/提高-
知识点
题目描述
A median of an array of integers of length $n$ is the number standing on the $\lceil {\frac{n}{2}} \rceil$ (rounding up) position in the non-decreasing ordering of its elements. Positions are numbered starting with $1$ . For example, a median of the array $[2, 6, 4, 1, 3, 5]$ is equal to $3$ . There exist some other definitions of the median, but in this problem, we will use the described one.
Given two integers $n$ and $k$ and non-decreasing array of $nk$ integers. Divide all numbers into $k$ arrays of size $n$ , such that each number belongs to exactly one array.
You want the sum of medians of all $k$ arrays to be the maximum possible. Find this maximum possible sum.
Given two integers $n$ and $k$ and non-decreasing array of $nk$ integers. Divide all numbers into $k$ arrays of size $n$ , such that each number belongs to exactly one array.
You want the sum of medians of all $k$ arrays to be the maximum possible. Find this maximum possible sum.
输入格式
The first line contains a single integer $t$ ( $1 \leq t \leq 100$ ) — the number of test cases. The next $2t$ lines contain descriptions of test cases.
The first line of the description of each test case contains two integers $n$ , $k$ ( $1 \leq n, k \leq 1000$ ).
The second line of the description of each test case contains $nk$ integers $a_1, a_2, \ldots, a_{nk}$ ( $0 \leq a_i \leq 10^9$ ) — given array. It is guaranteed that the array is non-decreasing: $a_1 \leq a_2 \leq \ldots \leq a_{nk}$ .
It is guaranteed that the sum of $nk$ for all test cases does not exceed $2 \cdot 10^5$ .
The first line of the description of each test case contains two integers $n$ , $k$ ( $1 \leq n, k \leq 1000$ ).
The second line of the description of each test case contains $nk$ integers $a_1, a_2, \ldots, a_{nk}$ ( $0 \leq a_i \leq 10^9$ ) — given array. It is guaranteed that the array is non-decreasing: $a_1 \leq a_2 \leq \ldots \leq a_{nk}$ .
It is guaranteed that the sum of $nk$ for all test cases does not exceed $2 \cdot 10^5$ .
输出格式
For each test case print a single integer — the maximum possible sum of medians of all $k$ arrays.
输入输出样例
输入 #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
说明/提示
The examples of possible divisions into arrays for all test cases of the first test:
Test case $1$ : $[0, 24], [34, 58], [62, 64], [69, 78]$ . The medians are $0, 34, 62, 69$ . Their sum is $165$ .
Test case $2$ : $[27, 61], [81, 91]$ . The medians are $27, 81$ . Their sum is $108$ .
Test case $3$ : $[2, 91, 92, 95], [4, 36, 53, 82], [16, 18, 21, 27]$ . The medians are $91, 36, 18$ . Their sum is $145$ .
Test case $4$ : $[3, 33, 35], [11, 94, 99], [12, 38, 67], [22, 69, 71]$ . The medians are $33, 94, 38, 69$ . Their sum is $234$ .
Test case $5$ : $[11, 41]$ . The median is $11$ . The sum of the only median is $11$ .
Test case $6$ : $[1, 1, 1], [1, 1, 1], [1, 1, 1]$ . The medians are $1, 1, 1$ . Their sum is $3$ .
Test case $1$ : $[0, 24], [34, 58], [62, 64], [69, 78]$ . The medians are $0, 34, 62, 69$ . Their sum is $165$ .
Test case $2$ : $[27, 61], [81, 91]$ . The medians are $27, 81$ . Their sum is $108$ .
Test case $3$ : $[2, 91, 92, 95], [4, 36, 53, 82], [16, 18, 21, 27]$ . The medians are $91, 36, 18$ . Their sum is $145$ .
Test case $4$ : $[3, 33, 35], [11, 94, 99], [12, 38, 67], [22, 69, 71]$ . The medians are $33, 94, 38, 69$ . Their sum is $234$ .
Test case $5$ : $[11, 41]$ . The median is $11$ . The sum of the only median is $11$ .
Test case $6$ : $[1, 1, 1], [1, 1, 1], [1, 1, 1]$ . The medians are $1, 1, 1$ . Their sum is $3$ .