#P17991. Multiset Variance

Multiset Variance

Multiset Variance

题目描述

给定 nn 个整数多重集。你可以将每个输入多重集完整地取任意非负整数次,再把这些元素合并成一个非空多重集。求所得多重集方差的最小值与最大值。

对多重集 X={x1,…,xk}X=\{x_1,\ldots,x_k\},均值和方差定义为

$$E(X)=\frac1k\sum_{i=1}^{k}x_i,\qquad \operatorname{Var}(X)=\frac1k\sum_{i=1}^{k}(x_i-E(X))^2.$$

重复的元素按其出现次数计入。可以证明最小值和最大值均能够由某种有限的选取方案取得。

输入格式

第一行一个整数 tt,表示测试用例数。

每个测试用例的第一行是整数 nn。接下来 nn 行分别描述一个多重集:先给出其大小 kk,再给出 kk 个整数。

输出格式

输出 tt 行,每行两个实数,依次表示最小方差和最大方差。

对于每个数,设精确答案为 RR、输出为 SS,必须满足

∣S−R∣≤10−11max⁡(1,R).|S-R|\le10^{-11}\max(1,R).

小数点后最多输出 2020 位数字。

数据范围

1≤t≤10001\le t\le1000,每组 1≤n≤1051\le n\le10^5;每个多重集的大小 1≤k≤101\le k\le10,元素为 [−2×105,2×105][-2\times10^5,2\times10^5] 中的整数。

所有测试用例中,所有多重集的大小之和不超过 10610^6。

样例输入

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

第三组的最大方差为 25/925/9,可以由 {1,3}\{1,3\} 取五次、{5}\{5\} 取八次得到。