51Nod - 1098 最小方差
第1行：2个数M,N，(M > N, M <= 10000) 第2 - M + 1行：M个数的具体值(0 <= Xi <= 10000)
输出最小方差 * N的整数部分。
5 3 1 2 3 4 5
2
题解：
求 x(i+1) + x(i+2) + ... + x(i+2) 的平方差，
(x[i+1] - avg)^2 + (x[i+2] - avg)^2 + ... + (x[i+n] - avg)^2 = (x[i+1] ^ 2 + x[i+2]^2 + .. + x[i+n]^2 - 2*avg*(x[i+1] + ... + x[i+n]) + n*avg*avg )
根据这个可以将时间由O(n*m) 缩小到O(n)
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
using namespace std;
const int MAXN = 10000 + 10;
int n, m, num[MAXN], pow2[MAXN];
int cmp(const void *a, const void *b){
return (*(int *)a - *(int *)b);
}
int main(){
long long ans, sum_power, sum_num, tmp;
double avg;
while(scanf("%d %d", &m, &n) != EOF){
for(int i=0; i<m; ++i){
scanf("%d", &num[i]);
}
qsort(num, m, sizeof(num[0]), cmp);
for(int i=0; i<m; ++i){
pow2[i] = num[i] * num[i];
}
sum_num = 0;
sum_power = 0;
for(int i=0; i<n; ++i){
sum_num += num[i];
sum_power += pow2[i];
}
avg = sum_num *1.0 / n;
ans = (long long)(sum_power - 2*avg*sum_num + n*avg*avg);
for(int i=n; i<m; ++i){
sum_num += num[i] - num[i-n];
sum_power += pow2[i] - pow2[i-n];
avg = sum_num *1.0 / n;
tmp = (long long)(sum_power - 2*avg*sum_num + n*avg*avg);
if(tmp < ans){
ans = tmp;
}
}
printf("%lld\n", ans );
}
return 0;
}
原文：http://www.cnblogs.com/zhang-yd/p/6910639.html