さいしょうぶんさん

x 1,x 2,x 3なら...xnの平均数はkである.
分散s^2=1/n*[(x 1-k)^2+(x 2-k)^2+......+(xn-k)^2]となる.
分散は平方からずれた平均値であり、標準差または平均分散と呼ばれ、分散は変動の程度を記述する.
M個の数を与え,そこからN個の数を探し出し,このN個の数の分散を最小にする.
Input

 1 ：2  M,N，(M > N, M <= 10000)
 2 - M + 1 ：M      (0 <= Xi <= 10000)

Output

       * N     。

Input例

5 3
1
2
3
4
5

Outputの例
2

#include 
#include 
using namespace std;

typedef long long int ll;
const int MAXN = 10005;
int M, N;
int input[MAXN];
ll sum[MAXN];

int main()
{
    cin >> M >> N;
    input[0] = 0;
    for (int i = 1; i <= M; i++)
    {
        cin >> input[i];
    }
    sort(&input[1], &input[M + 1]);
    sum[0] = 0;
    for (int i = 1; i <= M; i++)
    {
        sum[i] = sum[i - 1] + input[i];
    }
    
    double result = 0x3FFFFFFFFFFFFFFF;
    for (int i = N; i <= M; i++)
    {
        double aver = (sum[i] - sum[i - N]) * 1.0 / N;
        double temp = 0;
        for (int j = i - N + 1; j <= i; j++)
        {
            temp += (input[j] - aver) * (input[j] - aver);
        }
        
        if (temp < result)
        {
            result = temp;
        }
    }
    
    cout << (ll)result << endl;
    
	return 0;
}