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

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

2012-01-18 CommonMan

说实话，这是一个功课题吗？ – 2012-01-18 17:59:53

你有什么尝试？它有用吗？你有没有例子输入和输出的测试用例？ – 2012-01-18 18:00:14

这听起来更像是一个面试问题，而不是一个容易的问题 – BrokenGlass 2012-01-18 18:05:14

您可以将此问题减少到sum-subset problem - 也cached here。这是主意。

让A为数组。计算S = A[0] + ... + A[N-1]，其中N是A的长度。对于k，从1到N-1，请让T_k = S * k/N。如果T_k是整数，则找到大小为k的A的子集，其总和为T_k。如果你能做到这一点，那么你就完成了。如果您无法对k执行此操作，则不存在此类分区。

这是这种方法背后的数学。假设有一个分区A，这样两部分的平均值相同，说大小的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大小的子集的总和。

来源

2012-01-18 19:07:47 PengOne

经过一番思考后，我仍然没有看到你的证明如何减少子集总和OP的问题。 – soulcheck 2012-01-18 19:45:33

我的意思是，你必须证明，有子集总和的答案可以回答OP的问题，而不是相反。 – soulcheck 2012-01-18 19:57:16

@soulcheck我仍在思考他们是否真的相当。我相信答案归结为[我刚刚问过这个问题]（http://stackoverflow.com/questions/8916539/sum-subset-with-a-fixed-subset-size）。 – PengOne 2012-01-18 19:59:14

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

回答

相关问题