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

题目描述

一个班级有 NN 名学生。第 ii 名学生的能力值为 AiA_i。

老师要将这些学生分为恰好 KK 个小组。每名学生必须恰好属于一个小组,每个小组必须至少有一名学生。

一个小组的实力定义为该组学生能力值的平均值。老师希望使这 KK 个小组的实力之和最大。

求这 KK 个小组的实力之和的最大值。

输入格式

输入包含多组测试数据,格式如下:

T
case_1
case_2
...
case_T

每组测试数据的格式如下:

N K
A_1 A_2 ... A_N

第一行包含一个整数 TT(1≤T≤2×1051\le T\le 2\times 10^5),表示测试数据组数。

每组测试数据的第一行包含两个整数 NN 和 KK(1≤K≤N≤2×1051\le K\le N\le 2\times 10^5),分别表示学生人数和小组数量。

每组测试数据的第二行包含 NN 个整数 A1,A2,…,ANA_1,A_2,\ldots,A_N(1≤Ai≤1091\le A_i\le 10^9),其中 AiA_i 表示第 ii 名学生的能力值。

所有测试数据的 NN 之和不超过 2×1052\times 10^5。

输出格式

对于每组测试数据,在单独一行输出 KK 个小组的实力之和的最大值。当你的答案的绝对误差或相对误差不超过 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