#ZS20244. 最小方差

最小方差

4. 最小方差(count.cpp)

题目描述: 有一天舟舟想起了一个统计公式。定义一个长度为m的序列,我们可以得到v, v的计算如下: $ V = \frac{(x_1 - \overline{x})^2+(x_2 - \overline{x})^2+\cdots+(x_m - \overline{x})^2}{m} $

其中: x=(x1+x2++xm)m \overline{x} = \frac{(x_1 + x_2+\cdots+x_m)}{m} ,即m个数的平均数

现在给你n个整数,需要从中选出m个数,使得这m个数的v值最小。

为了方便,使答案是整数,请输出m2vm^2*v

输入格式:

  • 第一行两个整数n和m。
  • 接下来n行,每行一个整数,表示给定的n个数。

输出格式:

  • 输出一个整数表示答案,保证不超过long long。

示例输入1:

5 3
1
2
3
4
5

示例输出1:

6

数据范围约定 总计 10个测试点。

  • 对于20%的数据,保证1mn101 \le m \le n \le 10
  • 对于50%的数据,保证1mn1031 \le m \le n \le 10^3
  • 对于100%的数据,保证1mn105,0xi1041 \le m \le n \le 10^5, 0 \le x_i \le 10^4