您如何将一个数组分成两部分，以使这两部分具有相等的平均值？

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

您可以将此问题简化为总和子集问题

-也在此处缓存。这是主意。

设A数组。计算的长度S = A[0] + ... +

A[N-1]在哪里。对于从到，让。如果是整数，则找到总和为的大小子集。如果可以这样做，那么您就完成了。如果您不能对任何一个执行此操作，则不存在此类分区。N``A``k``1``N-1``T_k

= S * k / N``T_k``A``k``T_k``k

这是这种方法背后的数学原理。假设存在一个A这样的分区，使得两个部分的平均值相同，X即size的大小x，Y而size

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。