#P17991. Multiset Variance
Multiset Variance
Multiset Variance
题目描述
给定 个整数多重集。你可以将每个输入多重集完整地取任意非负整数次,再把这些元素合并成一个非空多重集。求所得多重集方差的最小值与最大值。
对多重集 ,均值和方差定义为
$$E(X)=\frac1k\sum_{i=1}^{k}x_i,\qquad \operatorname{Var}(X)=\frac1k\sum_{i=1}^{k}(x_i-E(X))^2.$$重复的元素按其出现次数计入。可以证明最小值和最大值均能够由某种有限的选取方案取得。
输入格式
第一行一个整数 ,表示测试用例数。
每个测试用例的第一行是整数 。接下来 行分别描述一个多重集:先给出其大小 ,再给出 个整数。
输出格式
输出 行,每行两个实数,依次表示最小方差和最大方差。
对于每个数,设精确答案为 、输出为 ,必须满足
小数点后最多输出 位数字。
数据范围
,每组 ;每个多重集的大小 ,元素为 中的整数。
所有测试用例中,所有多重集的大小之和不超过 。
样例输入
3
3
2 1 3
4 1 2 2 3
2 3 5
2
3 -3 0 0
3 -2 -2 1
2
2 1 3
1 5
样例输出
0.5 2
2 2
0 2.777777777778
第三组的最大方差为 ,可以由 取五次、 取八次得到。