1098 最小方差

若x1,x2,x3......xn的平均数为k。

则方差s^2 = 1/n * [(x1-k)^2+(x2-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 312345

Output示例

2

先排序，计算前n个的方差。然后[1,n+1]之间的方差可以在[1,n]的基础上得到。

设k为(a₁+a₂+...+a_n)/n  s² = [(a₁-k)²+(a₂-k)²+...+(a_n-k)²]   就不除以n了，因为答案要乘以n

现在计算[1,n+1]的方差，现在的平均数变成了k + (a_n+1-a₁)/n 

设(a_n+1-a₁)/n 为x ,即s²' =  [(a₂-k-x)²+(a₃-k-x)²+...+(a_n+1-k-x)²] 

展开为s²' = [(a_n+1-k-x)2 + (a₂-k)² - 2x(a₂-k)² - 2x(a₃-k)² - ... - 2x(a_n-k)²+(n-1)x²)]

s²' - s² = (a_n+1-k-x)² - (a₁-k)² + 2x(a₁-k) + (n-1)x²

所以后面的方差可以根据前面的得到，复制度就是O(nlogn)了，主要是排序占时间，只要扫描一遍。

1 #include 
       
         2 using namespace std; 3 const int N = 1e4+10; 4 int a[N]; 5 int main() { 6     int n, m; 7     cin >> m >> n; 8     for(int i = 0; i < m; i ++) cin >> a[i]; 9     sort(a, a+m);10     double s = 0, sum = 0;11     for(int i = 0; i < n; i ++) sum += a[i];12     double k = sum/n;13     for(int i = 0; i < n; i ++) {14         s += 1.0*(a[i]-sum/n)*(a[i]-sum/n);15     }16     double ss = s;17     for(int i = n; i < m; i ++) {18         double x = 1.0*(a[i]-a[i-n])/n;19         s = s + (a[i]-k-x)*(a[i]-k-x)-(a[i-n]-k)*(a[i-n]-k)+2*x*(a[i-n]-k)+x*x*(n-1);20         ss = min(ss,s);21         k = x+k;22     }23     printf("%.0f\n",floor(ss));24     return 0;25 }