HDU5734:Acperience（方差）

题意：

给出n个数xi，确定一个值α，使得Σ(xi-α)^2的值最小。

---

分析：

可以猜想是方差，不懂得可以去方差了解一下。

那么α即为∑(xi)/n,然后要注意的是转化为分数，首先我们不能用小数转分数做（double精度会丢失，你可以尝试一下），然后就想到将式子同分母，再求分子分母的gcd，最后分子分母同除gcd，答案就出来啦。

式子为 ：

(x1^2+x2^2+---+xn^2)-2α(x1+x2+---+xn)+nα^2,α=∑(xi)/n;

然后同分母，使得分母为n，即：

（∑(xi^2)*n)-n*(x1+x2+---+xn)^2即为分子，分母为n，然后就好了。

---

代码：

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL __int64
#define For(i,a,b) for (int i=(a),_##i=(b); i<=_##i; i++)
int t;
LL n,a[100010];

inline LL gcd(LL a,LL b)
{
    return (b==0)?a:gcd(b,a%b);
}
int main()
{
    for(scanf("%d",&t);t--;){
        scanf("%I64d",&n);
        For(i,1,n) {scanf("%I64d",a+i);a[i]=abs(a[i]);}
        LL ave=0,tot=0;
        For(i,1,n) {
            ave+=a[i];tot+=a[i]*a[i];
        } ave=ave*ave;
        LL sum=0;sum=(n*tot-ave);
        if(tot<(sum/n)) printf("%I64d/1
",tot);
        else
        {
            LL m=gcd(sum,n);
            printf("%I64d/%I64d
",sum/m,n/m);
        }
    }
    return 0;
}