Что спрашивают
Посетитель вида 1 или 2 идёт в соответствующее окно; вида 0 — в более короткую очередь, при равенстве в окно 1. В длину очереди включается обслуживаемый. Если в выбранной очереди уже четыре человека, новый посетитель уходит.
Приходы обрабатываются по времени, при равенстве в исходном порядке. Завершившиеся ровно к приходу уже ушли. Найдите число обслуженных окном 2 и число отказов. N ≤ 100 000; обслуживание длится от 1 до 10 000.
Приём решения
В каждой очереди храним времена завершения обслуживания уже принятых посетителей. Они строго возрастают: обслуживание последовательное, длительности положительны. Удобна deque с быстрым удалением первого элемента.
Перед каждым приходом t удалим из обеих очередей все завершения <= t. Затем по виду услуги и текущим длинам выберем окно. Если длина равна четырём, увеличим отказы. В другую очередь отказавший посетитель не переходит.
Иначе время нового завершения равно max(t, последнее завершение очереди) + duration. Для пустой очереди обслуживание начинается в t. Каждый принятый в окно 2 сразу увеличивает его счётчик: по условию все вставшие в очередь будут обслужены.
Сортировка только по времени в Python стабильна, поэтому сохраняет исходный порядок равных приходов. Каждый элемент удаляется один раз. Время O(N log N), память O(N) на вход и сортировку; сами очереди содержат не более восьми времён.
Разбор на примере
Ввод
9 10 1 0 0 10 1 0 10 1 0 10 1 0 10 1 0 1 1 0 1 0 3 1 2 1 2 0
Вывод
4 1
| Приход | Очереди перед выбором | Действие |
|---|---|---|
| 0, первые четыре вида 1 | Окно 1: от 0 до 3 | Завершения 10, 20, 30, 40 |
| 0, пятый вида 1 | 4 и 0 | Отказ |
| 0, вид 0 | 4 и 0 | Окно 2 до 1 |
| 1, вид 0 | 4 и 0 | Окно 2 до 3 |
| 3, вид 2 | 4 и 0 | Окно 2 до 4 |
| 10, вид 0 | 3 и 0 | Окно 2 до 11 |
В момент 0 первые четыре посетителя вида 1 занимают очередь окна 1; пятый получает отказ. Посетитель вида 0 выбирает пустое окно 2 и заканчивает в 1. Следующие приходы в 1 и 3 тоже обслуживаются окном 2. В момент 10 в окне 1 остаются трое, а окно 2 свободно: пришедший выбирает его. Всего окно 2 примет четверых.
Код на Python и C++
Не сортируйте полные тройки: при одинаковом времени это изменит порядок по длительности и виду услуги. Ключ сортировки содержит только время.
В C++ sort не сохраняет порядок равных элементов, поэтому для сортировки по времени нужен stable_sort. Очереди — deque<long long>.
from collections import deque
import sys
def solve(visitors):
queues = [deque(), deque()]
served2 = rejected = 0
for time, duration, kind in sorted(visitors, key=lambda row: row[0]):
for queue in queues:
while queue and queue[0] <= time:
queue.popleft()
if kind:
window = kind - 1
else:
window = 0 if len(queues[0]) <= len(queues[1]) else 1
queue = queues[window]
if len(queue) == 4:
rejected += 1
continue
start = max(time, queue[-1]) if queue else time
queue.append(start + duration)
if window == 1:
served2 += 1
return served2, rejected
if __name__ == '__main__':
data = list(map(int, sys.stdin.buffer.read().split()))
visitors = list(zip(data[1::3], data[2::3], data[3::3]))
print(*solve(visitors))
<algorithm>
<deque>
<iostream>
<tuple>
<vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<tuple<long long, long long, int>> visitors(n);
for (auto& [time, duration, kind] : visitors)
cin >> time >> duration >> kind;
// stable_sort сохраняет исходный порядок людей, пришедших одновременно.
stable_sort(visitors.begin(), visitors.end(),
[](const auto& x, const auto& y) { return get<0>(x) < get<0>(y); });
deque<long long> queues[2];
int served2 = 0, rejected = 0;
for (auto [time, duration, kind] : visitors) {
for (auto& queue : queues) {
while (!queue.empty() && queue.front() <= time)
queue.pop_front();
}
int window;
if (kind)
window = kind - 1;
else
window = queues[0].size() <= queues[1].size() ? 0 : 1;
deque<long long>& queue = queues[window];
if (queue.size() == 4) {
rejected += 1;
continue;
}
long long start = queue.empty() ? time : max(time, queue.back());
queue.push_back(start + duration);
if (window == 1)
served2 += 1;
}
cout << served2 << ' ' << rejected << endl;
}
Типичные ошибки
- Не считать обслуживаемого в очереди
Ограничение четыре включает человека у окна. Длина deque уже учитывает его.
- Сначала поставить нового, потом удалить ушедших
Завершение в момент t происходит до выбора новым посетителем. Сначала удалите все времена не больше t.
- Выбирать по ближайшему освобождению
Для вида 0 сравниваются числа людей, а не суммарное ожидание. При равенстве выбирается окно 1.