минимальные ходы, чтобы сбалансировать массив - PullRequest
Новая
       4

минимальные ходы, чтобы сбалансировать массив

3 голосов
/ 17 февраля 2012

У нас есть массив из n натуральных чисел.Приемлемым шагом является увеличение элемента на 1 и уменьшение одного из его соседей на 1.

Минимальное и максимальное значение в конечном массиве должно отличаться не более чем на 1. Какое минимальное количество шагов для этого?

Например, если начальный массив равен {5, 6, 4, 1, 10}, ответом будет 5, а окончательный массив может быть {5, 5, 5, 5, 6}.

1 Ответ

2 голосов
/ 14 марта 2012

Мы можем использовать «Разделяй и властвуй» для этой проблемы.

Мы знаем, что конечное значение всех элементов должно быть СРЕДНЕМ всех элементов в массиве. Если среднее значение не является целым числом, то мы можем определить два значения - MAX и MIN, так что MAX - это потолок среднего, а MIN - пол среднего. (http://en.wikipedia.org/wiki/Floor_and_ceiling_functions)

Теперь разделите массив на 2 равные части. [0 - n / 2] и [n / 2 +1 к n-1]. Если n нечетно, первая половина будет меньше, но это не имеет значения.

Для каждой половины вычислите среднее значение всех элементов. Это среднее значение ДОЛЖНО быть равно МАКС. Или МИН. Если нет, это среднее значение должно быть либо увеличено, либо уменьшено по мере необходимости.

Теперь следует отметить, что среднее значение подмассива НЕ МОЖЕТ быть изменено операциями с элементами только внутри этого подмассива. Таким образом, любые изменения потребуют операций между n / 2-м и n / 2 + 1-м элементом.

Еще один момент, на который следует обратить внимание: если у одного подмассива среднее меньше, чем требуется, то у другого подмассива среднее больше, чем требуется.

Таким образом, можно легко выполнить соответствующую операцию между двумя средними элементами.

Теперь разделите каждый подмассив на две части и повторите процесс.

[ПРИМЕЧАНИЕ. Повторные операции суммирования, необходимые для вычисления средних значений подмассивов, могут выполняться в логарифмическом времени как для операций обновления, так и для операций суммирования с использованием дерева интервалов http://en.wikipedia.org/wiki/Interval_tree]

...