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

Question

如何将一个数组分成两个部分，使得这两部分的平均值相等？每个部分可能包含在数组中不连续的元素。 我所知道的唯一算法是指数级别的，我们能否做得更好？

- CommonMan

---

你诚实地说，这是一道作业题吗？ - Brian Driscoll

你尝试了什么？是否生效？你有一些带有示例输入和输出的测试用例吗？ - Greg Hewgill

这听起来更像是一道面试题，而且不是那种简单的。 - BrokenGlass

你能想到的算法是什么呢？ - YXD

暴力测试所有子集能够计算出一个解（如果存在的话），但这是O(2**N)。 - BrokenGlass

Answer 1

你可以将这个问题简化为 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的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 的子集之和。

- PengOne

---

经过一番思考，我仍然看不出你的证明如何将子集和问题归约到 OP 的问题。 - soulcheck

我的意思是，你基本上证明了如果有子集和问题的答案，就可以回答OP的问题，而不是相反。 - soulcheck

@soulcheck 我仍在思考它们是否真正等价。我相信答案归结于我刚刚提出的这个问题。 - PengOne

@PengOne，我有点困惑能否使用求和子集问题来找到大小为k且总和为T_k的集合。如果有多个不同大小的集合其总和均为T_k，且其中一个集合的大小为k，那该怎么办呢？我们是否可以调整求和子集问题的方法来确定是否存在大小为k的集合？ - NPE

@PengOne 这个问题有解决方案吗？我按照这个方法写了一段代码，但是它输出的结果是错误的。我的代码链接：https://ideone.com/HadH3V - user248884