Все задачи
Средне Решено: 0 Процент решений: 0%

Моделирование очереди в банке

Смоделируйте клиентов, ожидающих в одной очереди к нескольким кассирам банка, и выведите время ожидания.

Чему вы научитесь

  • Обслуживать клиентов в порядке живой очереди
  • Отслеживать, когда освобождается каждый кассир
  • Собирать итоговую статистику моделирования

Условие

В банке работают tellers кассиров, а очередь одна. Клиент i приходит в минуту arrivals[i], и его обслуживание занимает service[i] минут. Клиентов обслуживают строго в порядке прихода (в порядке списков). Когда клиент оказывается первым в очереди, он идёт к кассиру, который освободится раньше всех (при равенстве - к кассиру с меньшим номером), и начинает обслуживаться в более поздний из двух моментов: время своего прихода или время, когда кассир освободится. Все кассиры свободны с минуты 0.

Ожидание клиента - это время начала обслуживания минус время прихода.

Реализуйте bank_queue_simulation(arrivals, service, tellers).

Входные данные

arrivals: минуты прихода в неубывающем порядке.

service: время обслуживания каждого клиента в минутах, в том же порядке.

tellers: количество кассиров.

Выходные данные

Верните [total_wait, longest_wait, last_finish]: сумму всех ожиданий, самое долгое ожидание и минуту, когда закончится обслуживание последнего клиента. Если клиентов нет, верните [0, 0, 0].

Ограничения

0 ≤ количество клиентов ≤ 2000

0 ≤ arrival ≤ 100 000

1 ≤ service ≤ 1000

1 ≤ tellers ≤ 20

Примеры

Пример 1
Ввод:
arrivals = [0, 1, 2, 3]
service = [5, 3, 4, 2]
tellers = 2

Ожидаемый вывод:
expected = [4, 2, 8]
Ввод:
std::vector<long long> arrivals = {0, 1, 2, 3};
std::vector<long long> service = {5, 3, 4, 2};
long long tellers = 2;

Ожидаемый вывод:
std::vector<long long> expected = {4, 2, 8};
Ввод:
long[] arrivals = new long[] {0, 1, 2, 3};
long[] service = new long[] {5, 3, 4, 2};
long tellers = 2;

Ожидаемый вывод:
long[] expected = new long[] {4, 2, 8};

Пояснение

Клиенты 1 и 2 начинают сразу (в 0 и в 1). Кассир 2 освобождается в 4, поэтому клиент 3 ждёт 2; кассир 1 освобождается в 5, поэтому клиент 4 ждёт 2. Последний клиент заканчивает в max(8, 7) = 8: [4, 2, 8].

Пример 2
Ввод:
arrivals = [0, 0, 0]
service = [4, 4, 4]
tellers = 1

Ожидаемый вывод:
expected = [12, 8, 12]
Ввод:
std::vector<long long> arrivals = {0, 0, 0};
std::vector<long long> service = {4, 4, 4};
long long tellers = 1;

Ожидаемый вывод:
std::vector<long long> expected = {12, 8, 12};
Ввод:
long[] arrivals = new long[] {0, 0, 0};
long[] service = new long[] {4, 4, 4};
long tellers = 1;

Ожидаемый вывод:
long[] expected = new long[] {12, 8, 12};

Пояснение

При одном кассире ожидания равны 0, 4 и 8, а последний клиент заканчивает в 12: [12, 8, 12].

Как подступиться

Сначала попробуйте сами, затем открывайте подсказки по одной.

Подсказка 1

Храните массив с минутой, когда освобождается каждый кассир.

Подсказка 2

Для каждого клиента выбирайте наименьшее время освобождения (при равенстве - наименьший индекс).

Подсказка 3

Начало обслуживания - более позднее из времени прихода и этого времени освобождения; ожидание - начало минус приход.

Ожидаемая сложность

время O(n × k), доп. память O(k)

Ссылки

Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.

Лучшее принятое решение каждого участника. Более быстрые, экономные и высоко оценённые решения стоят выше.

Принятых решений пока нет. Решите задачу и займите первое место.

Учитесь у других

Решения сообщества

Пока нет опубликованных решений. Решите задание, чтобы поделиться первым.