Алгоритм двоичного поиска для максимизации значений
Мне поручили эту проблему, которую я должен решить:
В определенном бассейне есть множество мероприятий с гидом. Поэтому правила использования очень строгие:
Свободное время занимает всего одну минуту. После использования свободного слота, мы должны подождать как минимум x секунд, прежде чем использовать другой слот. У вас есть список свободных слотов, и вы хотите плавать хотя бы m минут. Какой максимум x что позволяет?
вход
Вход состоит из нескольких случаев. Каждый случай начинается с количества минут m и количество слотов n, с последующим n троек H:M:Sуказывает на наличие полосы, которая свободна в течение одной минуты, начиная с H:M:S, Предполагать 2 ≤ m ≤ n ≤ 1000что часы между 00:00:00 а также 23:59:00и что между временными интервалами нет совпадений. Финальная запись отмечена специальным случаем с m = n = 0,
Выход
Для каждого случая выведите максимум x это позволяет общее время купания м или более минут.
Какова была бы возможная реализация, использующая бинарный поиск по переменной x, чтобы максимизировать его?
Выходы проблемы:
input:
4 8
00:10:40 00:35:30 01:00:00 01:55:00 02:10:00 03:15:00 12:00:20 23:59:00
output: x = 11000
Решение
Это не требует поиска вообще. Преобразуйте список из свободных временных интервалов в список времени ожидания между временными интервалами в секундах (учитывая, что вы плаваете в течение одной минуты):
waiting_time[]
for i in [1, length(time_slots))
waiting_time[i - 1] = delta_minutes(time_slots[i - 1], time_slots[i]) * 60 - 60
Сортировать список времени ожидания
sortDesc(waiting_time)
Так как ты должен ждать m - 1 раз, x должен быть выбран так, чтобы по крайней мере x время ожидания по крайней мере одинаково долго. Так как мы ищем максимум xНаименьшее время ожидания должно быть ровно столько, сколько x, какой m - 1й элемент в нашем массиве.
Собираем все вместе:
minX(input[], m):
waiting_time[]
for i in [1, length(input)):
waiting_time[i - 1] = delta_minutes(time_slots[i - 1], time_slots[i]) * 60 - 60
sortDesc(waiting_time)
return waiting_time[m - 1]
Другие решения
Других решений пока нет …