夜间模式
字体
阴影
滤镜
主题色
Luogu P2503 [HAOI2006]均分数据 题解

Link

题目传送门

题面

有$n$个数字$a_1,a_2,a_3\dots a_n$把他们分成$m$组,使得均方差最小。均方差公式如下:
$\sigma = \sqrt{\frac 1n \sum\limits_{i=1}^n(\overline x – x_i)^2},\overline x = \frac 1n \sum\limits_{i=1}^n x_i$

思路

显然如果告诉你这$n$个数字固定的排列顺序就一定可以贪心求出最小值:将当前的数加入到最小的组中。
所以只需要$random\text{_} shuffle$即可。

Code

暂无评论

发送评论


				
上一篇
下一篇