首先考虑最小值，由于方差就是 $\min_x \frac{1}{n}\sum_{i=1}^n (a_i-x)^2$，所以可以枚举 $x$，之后就是选若干个数，最小化平均值。所以方差最小值一定是在取单个集合的时候取到。

最大值仍然考虑枚举 $x$，这时要求平均值必须等于 $x$。设第 $i$ 个可重集为 $S_i$，$b_i=\frac{1}{|S_i|}\sum_{y\in S_i}(y-x),c_i=\frac{1}{|S_i|}\sum_{y\in S_i}(y-x)^2$，则相当于要找一组实数 $s_1,\ldots,s_n$，满足 $\sum b_is_i=0$，最大化 $\sum c_is_i$。这也就说明了方差一定能在只选两种集合的情况下取到最大值。

设选择的两个集合为 $S,T$，$s_1,t_1$ 分别为 $S,T$ 的平均值，$s_2,t_2$ 分别为 $S,T$ 的平方平均值。则需要找到 $p,q\ge 0,p+q=1$，最大化 $ps_2+qt_2-(ps_1+qt_1)^2$，这是关于 $p$ 的二次函数，一定在 $0,1$ 或对称轴处取得最值。进一步的，把 $(s_1,t_1)$ 和 $(s_2,t_2)$ 看作平面上的点，则我们需要选择线段上的一点 $(x,y)$，最大化 $y-x^2$。容易发现一定是在上凸包取到最大值。这也可以代替上面的分析说明一定取不超过两种集合。

时间复杂度 $O(n\log n)$。