如何将数组分成2个部分,使这两个部分具有相等的平均值？

Question

如何将数组分成2个部分,使这两个部分具有相等的平均值？每个分区可能包含数组中不连续的元素.我能想到的唯一算法是指数可以做得更好吗？

Answer 1

您可以将此问题减少到sum-subset问题 - 此处也缓存.这是个主意.

让我们A成阵.计算S = A[0] + ... + A[N-1],N长度在哪里A.对于k从1到N-1,让T_k = S * k / N.如果T_k是整数,则找到总和A的大小子集.如果你能做到这一点,那么你就完成了.如果您不能执行此操作,则不存在此类分区.kT_kk

这是这种方法背后的数学.假设存在一个分区,A使得两个部分具有相同的平均值,X大小x和Y大小y就是分区,其中x+y = N.那你必须有

sum(X)/x = sum(Y)/y = (sum(A)-sum(X)) / (N-x)

所以有点代数给出了

sum(X) = sum(A) * x / N

由于数组包含整数,因此左侧是整数,因此右侧也必须如此.这会激发T_k = S * k / N必须是整数的约束.唯一剩下的部分是实现T_k大小子集的总和k.