Выбор оптимального пути (python)

Question

Выбор оптимального пути (python)

Рейтинг: 0Ответов: 2Опубликовано: 16.02.2023

Задача: У Кати насыщенный день на работе. Ей надо передать n разных договоров коллегам. Все встре- чи происходят на разных этажах, а между этажами можно перемещаться только по лестничным пролетам — считается, что это улучшает физическую форму сотрудников. Прохождение каждого пролета занимает ровно 1 минуту. Сейчас Катя на парковочном этаже, планирует свой маршрут. Коллег можно посетить в любом порядке, но один из них покинет офис через t минут. С парковочного этажа лестницы нет — только лифт, на котором можно подняться на любой этаж. В итоге план Кати следующий: Подняться на лифте на произвольный этаж. Считается, что лифт поднимается на любой этаж за 0 минут. Передать всем коллегам договоры, перемещаясь между этажами по лестнице. Считается, что договоры на этаже передаются мгновенно. В первые t минут передать договор тому коллеге, который планирует уйти. Пройти минимальное количество лестничных пролетов. Помогите Кате выполнить все пункты ее плана.

Формат входных данных

В первой строке вводятся целые положительные числа n и t (2≤n,t≤100) — количество сотрудников и время, когда один из сотрудников покинет офис (в минутах). В следующей строке n чисел — номера этажей, на которых находятся сотрудники. Все числа различны и по абсолютной величине не превосходят 100. Номера этажей даны в порядке возрастания. В следующей строке записан номер сотрудника, который уйдет через t минут.

Формат выходных данных Выведите одно число — минимально возможное число лестничных пролетов, которое понадобится пройти Кате.

n, t = input().split()
string = input().split()
l = list(map(int, string))
num = int(input())
count = []

final = l[num-1]
difference = max(l) - min(l)
super = final - min(l)

if super > int(t):
    count1 = max(l) - min(l) + max(l) - final
    count2 = max(l) - min(l) + final - min(l)
    count.append(count1)
    count.append(count2)
    print(min(count))
else:
    print(difference)

Помогите, пожалуйста, понять что не так в коде. Многие тесты проходит, но на одном ступорит.

python поиск-пути

Источник: Stack Overflow на русском

Answer 1

▲ 1

Возможны следующие варианты:

final-min<=t - идём с начала до конца, время max-min

max-final<=t - идём с конца до начала, время max-min - вот этого я у вас не вижу

если оба эти условия не выполняются, едем на final, потом на ближайший из концов, время min(max-final, final-min) + max-min

И до кучи - в коде 9 раз производится поиск максимума и минимума в списке! Между тем при условии Номера этажей даны в порядке возрастания их искать вообще не нужно

Answer 2

▲ 0

Можете попробовать это:

floors = list(map(int, input().split()))
leaving_colleague = int(input())

destination_floor = floors[leaving_colleague - 1]

# Первый вариант: передать документ коллеге, который уходит
if t < n:  # если время t меньше, чем общее количество коллег
    floors.remove(destination_floor)  # убираем этаж, на котором находится уходящий коллега
    floors.append(destination_floor)  # добавляем его в конец списка
    n -= 1  # уменьшаем общее количество коллег на 1, так как уходящий коллега уже не требует передачи документов
    count1 = max(floors) - min(floors)  # минимальное количество лестничных пролетов без учета уходящего коллеги
    count2 = max(floors[:-1]) - min(floors[:-1]) + max([destination_floor, floors[-1]]) - min([destination_floor, floors[-1]])
    # минимальное количество лестничных пролетов, если сначала передать документ уходящему коллеге, затем остальным
    print(min(count1, count2))
else:  # если t больше или равно n, то уходящий коллега не нужно учитывать
    print(max(floors) - min(floors))

Выбор оптимального пути (python)

Ответы