塔子哥是一名数学家,他一直在研究一个关于序列划分的数学问题。他有一个长度为 n 的数组,数组中的每个元素都是一个非负整数。他想将这个数组划分成 k 个子序列,使得每个元素恰好在一个子序列中出现,且每个子序列都必须非空。他希望将这 k 个子序列的平均数之和尽可能地小,这样他就能够更深入地研究这个问题。
为了解决这个问题,塔子哥来到了你的面前,请求你帮助他找到一种最小化平均数之和的划分方案,使得这 k 个子序列的平均数之和尽可能小。你能帮帮他吗?
注,子序列可以不连续。例如数组为 [3,2,1,3] , k=2 时,子序列可以拆分为 [3,1] 和 [2,3]
第一行输入两个正整数 n 和 k ,代表数组的长度、子序列的数量。
第二行输入 n 个正整数 ai ,代表数组的元素。 保证序列不含重复元素
1≤k≤n≤105
−109≤ai≤109
一个小数,代表最终平均数之和的最小值。保留5位小数
输入
7 3
9 4 5 6 2 1 7
输出
9.20000
扫码备注加群即可,期待您的到来~
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.