A13946 | Sum of Medians
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
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$ .
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted