k序列平均值和最小

思路：

假设$k=1$时，只能分为$1$个。

$k=2$时，我们要需要分为两个数组，假设原数组为arr，分开后的数组为$arr1$,$arr2$,那么我们讨论$arr1$存有几个数最好。

其实只有一个数是最好的，且这个数最小才是最好的，即$arr1$只要一个最小数，其他$n-1$个数在$arr2$.

题目内容

小红是一名数学家，他一直在研究一个关于序列划分的数学问题。他有一个长度为 $n$ 的数组，数组中的每个元素都是一个非负整数。他想将这个数组划分成 $k$ 个子序列，使得每个元素恰好在一个子序列中出现，且每个子序列都必须非空。他希望将这 $k$ 个子序列的平均数之和尽可能地小，这样他就能够更深入地研究这个问题。

为了解决这个问题，小红来到了你的面前，请求你帮助他找到一种最小化平均数之和的划分方案，使得这 $k$ 个子序列的平均数之和尽可能小。你能帮帮他吗？

注，子序列可以不连续。例如数组为 $[3,2,1,3]$ ， $k=2$ 时，子序列可以拆分为 $[3,1]$ 和 $[2,3]$

输入描述

第一行输入两个正整数 $n$ 和 $k$ ，代表数组的长度、子序列的数量。

第二行输入 $n$ 个正整数 $a_i$ ，代表数组的元素。 保证序列不含重复元素

$1\le k\le n\le 10^5$

$-10^9\le a_i \le 10^9$

输出描述

一个小数，代表最终平均数之和的最小值。保留5位小数

样例

输入

7 3
9 4 5 6 2 1 7

输出

9.20000