题目描述：Given a nonnegative number set (can have duplicates), divide it into two sets so that the sum of the variances of these two sets is minimized. You can shuffle set order. The values of two sets cannot overlap. All number in the original set must appear in one of the two sets.
Finally return the value of the sum. The result include one decimal place.
The definition of variance: S^2= ∑ (X-a) ^2 / (n-1), where X is the average, a is every number in the set, and n is the size of the set.
For example: There is a set [1,3,1] . We can divide it into [1,1] and [3], Then return the result:0.0
Please simply proof the correctness of your solution.

时间复杂度要求O(nlgn)

求个解法。（目前想法是排序+前缀和枚举）但不知道咋证明，所以不知道对不对

提问于13天前

嘟嘟的神秘男友

545