powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Задача про очередь в банке
3 сообщений из 28, страница 2 из 2
Задача про очередь в банке
    #39920250
iOracleDev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Имя пользователя1
по сабжу, программерская:

В отделении банка работает K окон, в общей очереди стоит N человек, каждому из которых понадобится некоторое время обслуживания. Определить, через какое время после одновременного начала работы всех окон будут обслужены все посетители. Всё как обычно - окна начинают работать, к ним сразу подходят первые K челов, потом как только с кем-то разобрались, в освободившееся окно сразу ломится первый из очереди.

входные данные - N, K, массив длительностей. Например, N=3, K=2, arr = [4, 10, 5], ответ будет 10

Смысл задачи непонятен, процесс есть, управления им нет. Если в качестве задачи понимается наиболее быстро работающая
реализация имитационной модели, то с очередью мы ничего не можем делать, она тупо дает нам N итераций, на каждой итерации нам
нужно определить какое окно освобождается раньше, т.е. минимум текущего накопленного времени по всем окнам, отсюда следует, что
текущее накопленное время по окнам неплохо бы положить в деревянную структуру позволяющую поиск и добавление/изменение
элемента за O(logK), общая оценка O(NLogK).

По итерациям для [4, 10, 5], на первой итерации время по окнам 0, 4 идет в первое окно,
на второй итерации находим минимум по окнам 0 (второе окно), 10 идет во второе окно,
на третьей итерации минимум 4 (первое окно), 5 идет в первое окно,
на момент окончания очереди накопленное время по окнам 1-е окно 9, второе 10,
очередь полностью пройдет за максимальное накопленное время - 10.
...
Рейтинг: 0 / 0
Задача про очередь в банке
    #39920272
Фотография crutchmaster
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Имя пользователя1
переставить очередь таким образом, чтобы длительность была минимально возможной

Ну щас. Рассчитаешь ты сколько времени надо на клиента. Так бы и проблем не было. Да и это бессмысленно, т.к. окна всегда заняты и разница только в том, как обслужить хвост очереди так, чтобы работали оба окна. Т.е. разница будет не больше, чем у самого долгого клиента. Вот другой вопрос - минимизировать время ожидания в очереди так, чтобы оно было не больше времени обслуживания. Т.е. чтобы те, кому **действительно** только спросить не ждали всех.
...
Рейтинг: 0 / 0
Задача про очередь в банке
    #39920284
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
crutchmaster,

это просто техническая задача на квалификацию, ПОСЧИТАТЬ
не надо тут ничего минимизировать и тем более переставлять очередь

решается очень просто:
  • делаем бинарную кучу из первых K элементов (храним время завершения): O(K)
  • остатки очереди добавляем в кучу, заменяя минимальный - O((N-K) * ln(K))
Код: plaintext
1.
2.
3.
цикл:
  t = H[0]
  H[0] = t + M[i] 
  HeapUpdate(H, 0)

всё тупо и примитивно, нужно просто корректно реализовать
...
Рейтинг: 0 / 0
3 сообщений из 28, страница 2 из 2
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Задача про очередь в банке
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]