Получил эту проблему:
Имея массив целых чисел «башни», представляющий высоту некоторых блочных башен (в количестве блоков), необходимо написать код Python, чтобы расположить башни в виде восходящей или нисходящей ступенчатой шаблоны. Это означает, что высота каждой башни должна отличаться от высоты соседей ровно на 1, а вся последовательность должна быть строго возрастающей или убывающей. Чтобы изменить башни, вы можете сделать несколько ходов, добавляя только один блок на вершину любой башни. Ваша задача — найти минимальное количество ходов, необходимое для последовательного увеличения или уменьшения башен, в зависимости от того, какая последовательность требует меньшего количества ходов.
Пример: ввод towers=[1,4,3,2]
вывод 4
. Означает «нам нужно добавить 4 блока к вершине 1-й башни, чтобы получить последовательно более короткий массив [5,4,3,2]
»
Пример 2: ввод towers=[5,7,9,4,11]
вывод 9
. Означает «добавить 2 блока на вершину 1-й башни, + добавить 1 блок на вершину 2-й, + добавить 6 блоков на вершину 4-й башни», 9 = 2 + 1 + 6, чтобы получить окончательный массив [7,8,9,10,11]
».
Не нашел как решить, подскажите.
Не совсем, для меня все равно уже поздно :) Но хотелось бы обсудить или понять, как это сделать. И это было бы полезно для кого-то в будущем
Возьмите башни = [5,7,9,4,11]. рассмотрим опорную диагональ [0,1,2,3,4]. Различия [5,6,7,1,7]. Таким образом, мы должны переместить опорную диагональ вверх на 7. Она становится [7,8,9,10,11]. Затем он касается линии горизонта сверху, и разница с башнями составляет [2,1,0,6,0]. И 2 + 1 + 0 + 6 + 0 равно 9. Или вместо того, чтобы корректировать 5 разностей на 7, просто измените их сумму на 5 * 7.
Для [1,4,3,2] то же самое, но нам нужна нисходящая ссылка [0,-1,-2,-3]. Для каждого входа мы пробуем как по возрастанию, так и по убыванию, и находим лучший.
for towers in [1,4,3,2], [5,7,9,4,11]:
print(min(
max(d)*len(d) - sum(d)
for m in [-1,1]
for d in [[t-m*i for i, t in enumerate(towers)]]
))
Вывод (Попробуйте онлайн!):
4
9
Вместо нисходящей эталонной диагонали мы можем попробовать восходящую на перевернутой towers
. Также здесь я сначала определяю, насколько up
нам нужно сместить опорную диагональ, найдя максимальную tower - reference
разницу. Затем я начинаю с этой up
эталонной диагонали и суммирую reference - tower
разности.
for towers in [1,4,3,2], [5,7,9,4,11]:
print(min(
sum(r-t for r, t in enumerate(ts, start=up))
for ts in [towers, towers[::-1]]
for up in [max(t-r for r, t in enumerate(ts))]
))
В качестве альтернативы, также в линейном времени, но с постоянным пространством, просто выполните один проход по башням, отрегулируйте ссылку вверх всякий раз, когда текущая башня выше, и отслеживайте общее увеличение башни. Просто восходящая ссылка со вторым примером ввода:
towers = [5,7,9,4,11]
ref = total = 0
for i, tow in enumerate(towers):
if tow > ref:
total += i * (tow - ref)
ref = tow
total += ref - tow
ref += 1
print(total)
Может ли одна из башен быть нулевой? Что, если башни [0, 8, 2, 0, 9]
? Просто любопытно.
@DanielHao Да, почему бы и нет? Мое первое решение может обрабатывать даже отрицательные башни. (Мое только что добавленное второе решение предполагает неотрицательность, хотя при необходимости это можно решить.)
@ kelly-bundy Быстрый вопрос: как работает эта конструкция с 2 элементами «для» в первом решении и с 3 элементами «для»? Это не обычные циклы, верно?
@lugger1 Это выражение генератора с несколькими предложениями for
.
А, точно, точно...
Похоже, вы просите нас написать этот код для вас. Это не совсем цель этого сайта. Мы бы предпочли, чтобы вы написали его сами, с небольшой помощью. Итак, имея это в виду, каков ваш КОНКРЕТНЫЙ вопрос программирования в связи с этой проблемой?