2018/7/31--zznu-oj-问题 G: 方差 普拉斯--【两重暴力循环求方差即可！】

问题 G: 方差 普拉斯

时间限制: 1 Sec  内存限制: 128 MB
提交: 94  解决: 17
[提交] [状态] [讨论版] [命题人:admin]

题目描述

方差（样本方差）是每个样本值与全体样本值的平均数之差的平方值的平均数。在许多实际问题中，研究方差即偏离程度有着重要意义。
若x1,x2,x3......xn的平均数为k，则方差s^2 = 1/n * [(x1-k)^2+(x2-k)^2+.......+(xn-k)^2] 。
给出M个数，从中找出N个数，使这N个数方差最小。 
输入

第1行：2个数M,N，(M > N, M <= 10000)
第2 - M + 1行：M个数的具体值(0 <= Xi <= 10000)
输出

输出最小方差 * N的整数部分。 
样例输入

5 3
1
2
3
4
5
样例输出

2

---

大致思路：

　　1、求方差，暴力即可！暴力下来也只有两重for循环！不会超时！

　　2、设下标从x1--x2的n个数的方差为s1,平均数k1，下标x1+1—x2+1 的方差为s2，平均数为k2, 前后两者有一点联系，就是平均数会涉及到一些重复计算，分别设为k1和k2，k2=k1-x1/n+(x2+1)/n,省去了一些计算复杂度！但是，方差s1和s2并不能直接像类似于k1和k2那样直接转化!那么s2需要老老实实地再计算一遍！（我看着样例，直接得出了s1得到s2的式子！WA了一次！）因此时间复杂度不会因为一点k1得到k2的优化而发生变化！毕竟乘法时间复杂更大！

　　3、记得这个样本序列需要进行排序，升序排序一遍即可！不排序我WA了！

　　4、别被题面吓住了！尤其是开篇的两道题目造成的深深的心理阴影，后面的题目其实才简单呢！！！多做题，才能克服自己内心深处的恐惧！

　　5、会不会超double类型呢！貌似不会！假设（x1-k）等于1e4，那么平方会就是1e8，并且还有N个数，那个总的和就是1e12次方，基本会超过double了！不放心的话，可以在求xi的时候把（xi-k）*（xi-k）/N 调整成 （xi-k）/N*（xi-k），这样就肯定没问题了。

题解：

　　

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<string>
#include<vector>
#include<algorithm>
#define ll long long
using namespace std;
#define N 10000
#define ll long long
double a[N+10];

int main()
{
    int m,n;
    while(scanf("%d%d",&m,&n)!=EOF){
        for(int i=1;i<=m;i++)
            scanf("%lf",&a[i]);
        sort(a+1,a+1+m);
     //   for(int i=1;i<=m;i++)
     //       printf("*%lf  ",a[i]);

        a[0]=0;
        double sum=0,k=0,s2=0,ans=999999999.9;
        for(int i=1;i<n;i++)
            sum+=a[i];
        for(int i=n;i<=m;i++){
            sum=sum+a[i]-a[i-n];
            k=sum/n;
            s2=0;
            for(int j=i;j>=i-n+1;j--)
                s2=s2+(a[j]-k)/(1.0*n)*(a[j]-k);
            ans=min(ans,s2);
        }

        printf("%lld
",(ll)(ans*1.0*n+1e-8));

    }


    return 0;
}