33OJ
登录 注册

#P17536. [JAG 2026 Summer Camp #1] Group Strength

    ID: 20266 远端评测题 2000ms 2048MiB 尝试: 0 已通过: 0 显示难度普及− 上传者: 标签>贪心Special Judge排序ICPC2026

[JAG 2026 Summer Camp #1] Group Strength

Problem Description

There are NN students in a class. Student ii has an ability value of AiA_i.

The teacher will divide the students into exactly KK groups. Each student must belong to exactly one group, and each group must contain at least one student.

The strength of a group is defined as the average of the ability values of the students in that group. The teacher wants to maximize the sum of the strengths of the KK groups.

Find the maximum possible sum of the strengths of the KK groups.

Input Format

The input consists of multiple test cases in the following format.

T
case_1
case_2
...
case_T

Each test case is given in the following format.

N K
A_1 A_2 ... A_N

The first line contains an integer TT (1≤T≤2×1051\le T\le 2\times 10^5), the number of test cases.

The first line of each test case contains two integers NN and KK (1≤K≤N≤2×1051\le K\le N\le 2\times 10^5), the number of students and the number of groups, respectively.

The second line of each test case contains NN integers A1,A2,…,ANA_1,A_2,\ldots,A_N (1≤Ai≤1091\le A_i\le 10^9), where AiA_i represents the ability value of student ii.

The sum of NN over all test cases does not exceed 2×1052\times 10^5.

Output Format

For each test case, print the maximum possible sum of the strengths of the KK groups on a separate line. Your answer will be considered correct if its absolute or relative error does not exceed 10−710^{-7}.

3
6 3
23 5 41 12 9 30
9 5
37 4 91 18 52 11 73 26 45
7 4
17 17 17 17 17 17 17
83.25
280.2
68.0