Как разделить массив на 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 размера k, которое равно 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.