Непростая задачка на Python. Подскажите пожалуйста где ошибка
Вот всё что у меня получилось, но ничего не получилось :(
Подскажите пожалуйста где ошибка, или что переделать/сделать
def min_moves(n, m, platforms):
platforms.sort()
min_actions = 0
for i in range(1, m):
if platforms[i][0] > platforms[i - 1][1] + 1:
min_actions += platforms[i][0] - (platforms[i - 1][1] + 1)
platforms[i][0] = platforms[i - 1][1] + 1
return min_actions
n, m = map(int, input().split())
platforms = [tuple(map(int, input().split())) for _ in range(m)]
print(min_moves(n, m, platforms))
Условие: Все хорошее рано или поздно заканчивается, так подошел к концу и отдых Петра. Поэтому он прибыл на железнодорожный вокзал. Выглянув в окно, он увидел тренировочную площадку с рельсами.
Площадка представляет собой ? путей длины ? метров, которые располагаются параллельно рядом друг с другом, как показано на картинке.
На каждом пути стоит сцепка вагонов-платформ, каждый из которых имеет длину 1 метр. Гарантируется, что на каждом пути стоит ровно по одной сцепка, каждая из которых состоит из одной или нескольких сцепленных между собой вагонов-платформ.
Петр считает расстановку платформ практичной, если можно дойти от любой платформы до любой платформы по другим платформам. Переходить можно на соседние платформы на одном пути, а так же на соседние платформы на соседних по стороне путях.
Действием назовем движение смещение сцепки платформ на один метр в одну из сторон. При этом на одном пути можно сдвинуть только все вагоны одновременно.
За одно действие разрешается выбрать путь и сдвинуть сцепку вагонов на нем в одну из сторон на один метр. Сцепку можно перемещать, только если она не выходит за границы площадки.
Петр заинтересовался, какое минимальное количество действий необходимо сделать, чтобы расстановка платформ стала практичной.
Формат входных данных: В первой строке ввода даны два целых числа ? и ? - длина путей и количество путей (1 ⩽ ?, ? ⩽ 100_000). Гарантируется, что площадь площадки не превышает 10^6 (1 ⩽ ? ⋅ ?⩽ 1_000_000). В следующих ? строках записаны по два целых числа s? и t? - на каком расстоянии от начала располагается начальная и конечная платформа в ?-м пути площадки (1 ⩽ s? ⩽ t? ⩽ ?). Между начальной и конечной платформой тоже стоят платформы.
Формат выходных данных: Выведите единственное целое число — минимальное количество действий, которое необходимо сделать с вагонами, чтобы сделать расстановку практичной.
Замечание: В примере указана площадка, изображенная на картинке. Требуется сдвинуть сцепку на третьем пути на два метра вверх и сцепку из одного вагона на четвертом пути на два метра вниз. Всего пять действий
Примеры данных:
Вход:
7 5
1 4
2 3
6 7
2 2
4 7
7 5
1 4
2 3
6 7
2 2
4 7
Выход:
5
Ответы (1 шт):
Сортировка здесь совершенно не к месту. Задача не в том, чтобы переставить пути, и затем подвигать составы, сделав "лесенку", а сделать передвижку нужно на своих путях.
Пойдём по путям по очереди. Каждый состав k может находиться в n-l[k]+1 позициях, где l[k] - его длина, и стоимость позиции зависит от сдвига от начального положения. Для каждой из позиций найдём минимум из сочетаний с подходящими позициями левого k-1-го состава как стоимость позиции плюс минимум в параллельном отрезке для левого состава.
Таким образом, получается матрица размером mxn, содержащая в k-м столбце минимальные стоимости для создания всех позиций, и минимум в m-1 столбце есть нужный результат.
При прямой реализации получаем сложность до O(m*n^2), что явно много. Однако если при расчете минимумов для каждой позиции сохранять минимум в каждом отрезке (длиной в длину правого состава), то сложность будет O(m*n). Считать минимумы по отрезкам за O(1) можно, например, с помощью дека