Задача. Почти Ханойские башни
Лимит времени 1с.
Игровое поле представляет собой последовательность из N колонок по K
i фишек в каждой. За один ход с колонки с номером N
i можно забрать и переместить по m фишек в соседнюю левую и правую колонку. (2 * m ≤ K
i) С крайней левой и правой колонок разрешается перемещать фишки только в одну из соседних соответственно. Определите какое наименьшее количество разрешенных ходов нужно выполнить, чтобы в каждой колонке было равное количество фишек. Гарантируется что СУММ(K
i) / N всегда целое число.
входные данные
Первая строка входного файла содержит число N — количество колонок. В следующей строке записано K
i — количества фишек в каждой из колонок. (I принадлежит[1: N]) (2≤N≤200) (0≤Ki≤2000)
Исходные данные
Выходной файл должен содержать одно число — минимальное количество разрешенных ходов.
Input.txt Output.txt
5 7
5 2 4 8 16
Примечание
колонка 3 берем по 2, колонка 2 берем по 2, колонка 5 берем 16, колонка 4 берем по 13, колонка 3 берем по 7, колонка 5 берем 12, колонка 4 берем по 6.
Моя идея решения:
Дано:
1) вектор фишек v={5 2 4 8 16}
2) maxFish = СУММ(Ki);
Алгоритм:
"взвесить" левую left и правую right половины вектора вычислив для каждой стороны suma(v[i]-maxFish ) / N
если left<right тогда
Для каждой колонки i (слева направо)
f(i)=f(i-1)+(количество ходов для №i).
иначе
Для каждой колонки i (справа налево)
f(i)=f(i-1)+(количество ходов для №i).
answ = f(n)
Вопрос: как быстрее можно получить ответ задачи?