|
Задача про очередь в банке
|
|||
---|---|---|---|
#18+
Имя пользователя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. ... |
|||
:
Нравится:
Не нравится:
|
|||
30.01.2020, 01:05 |
|
Задача про очередь в банке
|
|||
---|---|---|---|
#18+
Имя пользователя1 переставить очередь таким образом, чтобы длительность была минимально возможной Ну щас. Рассчитаешь ты сколько времени надо на клиента. Так бы и проблем не было. Да и это бессмысленно, т.к. окна всегда заняты и разница только в том, как обслужить хвост очереди так, чтобы работали оба окна. Т.е. разница будет не больше, чем у самого долгого клиента. Вот другой вопрос - минимизировать время ожидания в очереди так, чтобы оно было не больше времени обслуживания. Т.е. чтобы те, кому **действительно** только спросить не ждали всех. ... |
|||
:
Нравится:
Не нравится:
|
|||
30.01.2020, 06:08 |
|
Задача про очередь в банке
|
|||
---|---|---|---|
#18+
crutchmaster, это просто техническая задача на квалификацию, ПОСЧИТАТЬ не надо тут ничего минимизировать и тем более переставлять очередь решается очень просто:
Код: plaintext 1. 2. 3.
всё тупо и примитивно, нужно просто корректно реализовать ... |
|||
:
Нравится:
Не нравится:
|
|||
30.01.2020, 07:53 |
|
|
start [/forum/topic.php?fid=16&gotonew=1&tid=1339838]: |
0ms |
get settings: |
12ms |
get forum list: |
15ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
190ms |
get topic data: |
14ms |
get first new msg: |
9ms |
get forum data: |
3ms |
get page messages: |
55ms |
get tp. blocked users: |
2ms |
others: | 14ms |
total: | 322ms |
0 / 0 |