P6069 『MdOI R1』Group

此题为比赛时的数据。 然鹅后来yummy觉得没这个必要，于是放弃加强。 **存在不使用`long double`和`__int128`的写法。**

为了让我们团队的同学更加团结，我们需要让各个成员的水平尽量平均。这时，就需要有人对自己产生一些改变。 我们的团队有 $n$ 个同学，第 $i$ 个同学的水平值是一个整数 $a_i$。 我们认为当整组同学水平值的 **方差** **不超过 $m$** 的时候，这组同学就是团结的。 请问至少要让几个同学改变自己的水平值（可以改成任意一个 **实数**），这个团队才可以做到团结？ 为避免读入时的精度误差，本题输入的 $m$ 是 **实际值的 $n$ 倍**，这个值是一个整数。 --- 如果你不知道什么叫做方差，以下是方差的基本概念： 方差是衡量一组数据 **波动程度** 的指标。 设长度为 $n$ 的序列 $a_{1\dots n}$ 的平均数为 $p$，则该序列的方差 $S$ 为： $$ S=\frac{1}{n} \sum_{i=1}^n(a_i-p)^2 $$

无

无

【样例 1 解释】 这组样例中，$n=4$，真实的 $m=\dfrac{32}{n}=8$。 一开始，所有同学水平值 $a_i$ 的平均数为 $1$，方差为： $$S=\dfrac{1}{4}[(3-1)^2+(7-1)^2+(-5-1)^2+(-1-1)^2]=20$$ 把第 $3$ 个同学的水平值改成 $3$ 后，平均数为 $3$，方差为： $$S=\dfrac{1}{4}[(3-3)^2+(7-3)^2+(3-3)^2+(-1-3)^2]=8$$ 只改变了 $1$ 人的水平值，即满足了题目要求。 【样例 2 解释】 这组样例中，$n=5$，真实的 $m=\dfrac{18}{n}=3.6$。 一开始，所有同学水平值 $a_i$ 的平均数为 $4.6$，方差为 $7.44$： 把第 $5$ 个同学的水平值改成 $3.5$ 后，平均数为 $3.5$，**方差为 $2.6$。** 只改变了 $1$ 人的水平值，即满足了题目要求。 --- 【数据范围】 |子任务编号|$n\leq$|分值| |:-:|:-:|:-:| |1|$16$|15| |2|$300$|17| |3|$10^3$|20| |4|$5\times 10^3$|7| |5|$10^4$|8| |6|$2\times 10^5$|33| 对于所有测试点，$1\leq n\leq 2\times 10^5$，$1\leq m\leq 10^{18}$，$0\leq |a_i|\leq 10^6$。