UVA10886 标准差 Standard Deviation 题解

因为要计算平均数和方差，所以需要算出每个 $x_i$ ，那么时间复杂度最少是 $O(n)$ 的。既然最少是 $O(n)$ 的，那么就直接与给定的公式和程序，先算出 $x_i$ 和 $m$ ，再算出来方差就行了。

注意如果不知道方差的话，一定要看英文题面，题面给的关于方差的式子其实是方差的平方。

代码：

#include <cstdio>
#include <cmath>
unsigned long long seed;
long double gen() {
    static const long double Z = ( long double )1.0 / (1LL<<32);
    seed >>= 16;
    seed &= ( 1ULL << 32 ) - 1;
    seed *= seed;
    return seed * Z;
}
int T, n;
long double a[10000003], m, s;
//s表示方差，注意都要用long double
int main() {
    scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++) {
        scanf("%d%llu", &n, &seed);
        m = 0.0, s = 0.0;//记得初始化
        for (int i = 1; i <= n; i++)
            a[i] = gen(), m += a[i];
        m /= n;
        for (int i = 1; i <= n; i++)
            s += (a[i] - m) * (a[i] - m);
        printf("Case #%d: %.5Lf\n", cas, (long double)sqrt(s / n));
    }
    return 0;
}