Задачник Базовый курс EN

Не больше R оповещений

скользящее окно очередь ограничение нагрузки в проде наука и физика

Служба рассылает оповещения о землетрясениях, но не больше r штук за любые t секунд подряд: если за последние t секунд уже отправлено r оповещений, новое событие оповещения не получает. Точнее: оповещение о событии в момент x отправляется, если среди уже отправленных оповещений меньше r таких, что были отправлены в моменты s с x − s < t. Сколько оповещений будет отправлено?

Тесты со второго по четвёртый — все землетрясения силой от пяти баллов за 2015–2025 годы из каталога USGS. В худшие сутки, после землетрясения магнитудой 8,8 у Камчатки в июле 2025 года, их было 166.

Вход

В первой строке n, r и t (1 ≤ n ≤ 2·10⁵, 1 ≤ r ≤ n, 1 ≤ t ≤ 10⁹). Во второй — n моментов событий в секундах, по неубыванию, от 0 до 10⁹.

Выход

Число отправленных оповещений.

Примеры

Пример 1

Вход

10 2 10
1 3 5 9 10 11 13 20 21 22

Выход

Ограничения

Время · Python: 4000 мс
Время · Go: 1000 мс
Память: 256 МБ
Проверка: 7 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Решение «отправлять или нет» зависит только от оповещений за последние t секунд. Какие из уже отправленных оповещений нужно помнить, и когда о них можно забыть?

2Идея

Держим очередь моментов отправленных оповещений. Перед каждым событием выбрасываем из головы очереди всё, что отправлено t секунд назад или раньше: это окно уже уехало. Если в очереди осталось меньше r, отправляем и кладём момент в хвост.

3Разбор

Моменты событий идут по неубыванию, поэтому очередь отсортирована сама: старые оповещения в голове, новые в хвосте, и выбрасывать нужно только с головы. В очереди никогда не бывает больше r элементов. Такой ограничитель называют скользящим журналом — он точнее всех, но помнит каждое оповещение в окне; подробнее о других способах — в статье об ограничении частоты.

Граница окна: оповещение, отправленное ровно t секунд назад, уже не считается (x − s < t). Пример из условия проверяет именно это.

3+Решение

4Сложность

Каждый момент один раз попадает в очередь и не больше одного раза из неё выходит: O(n) времени и O(r) памяти.

5Типичные ошибки

Фиксированные окна. Сбрасывать счётчик в начале каждого часа проще, но на стыке двух часов пропускает до 2r оповещений за t секунд — ответы расходятся.
Граница окна. «≥» и «>» при выбрасывании из очереди дают разные ответы, когда события идут ровно с шагом t.
Список вместо очереди в Python. pop(0) сдвигает весь список; при больших r это квадрат.

Алгоритмы задачи

TEC Приём Скользящее окно Окно ширины w ползёт по данным: ответ правится по входящему и уходящему элементу за O(1) вместо O(w). O(n) 2 задачи DS Структура данных Стек и очередь Стек: последним пришёл — первым ушёл. Очередь: первым пришёл — первым ушёл. Каждая операция — O(1). O(1) на push и pop, enqueue и dequeue 2 задачи SYS Алгоритм Ограничение частоты запросов Не больше N запросов в единицу времени: окно, журнал, два счётчика и ведро с токенами. O(1) на запрос (журнал — O(N)) 2 задачи