Два ограничителя
Служба уведомлений обещает подписчику не больше L сообщений за W секунд. Разработчики спорят, как это обеспечить, и проверяют два способа на одном и том же потоке событий.
- Окно по часам. Время делится на отрезки [kW, (k + 1)W). В каждом отрезке пропускаются первые L событий, остальные отбрасываются.
- Ведро с токенами. В ведре до L токенов, вначале оно полное, и каждые W/L секунд добавляется один токен (W делится на L). Событие проходит, если в ведре есть целый токен, и забирает его.
Для каждого способа выведите, сколько событий прошло, и сколько прошедших событий попало в самые насыщенные W секунд — в отрезок [s, s + W) при самом неудачном s. Среди тестов — уведомления о землетрясениях магнитудой 5 и больше за 2015–2025 годы.
Вход
В первой строке n, L и W (1 ≤ n ≤ 2·105, 1 ≤ L ≤ W ≤ 106, W делится на L). Во второй — моменты событий в секундах, по неубыванию: целые от 0 до 109; несколько событий могут прийти в одну секунду.
Выход
Две строки: для окна по часам и для ведра — число прошедших событий и наибольшее число прошедших за какие-нибудь W секунд.
Примеры
Пример 1
6 2 10 8 9 10 11 12 25
5 4 3 2
Пример 2
10 3 60 0 0 0 0 30 59 60 61 62 200
7 3 7 5
Ограничения
- Время · Python
- 3000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 8 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Окно по часам обещает «не больше L за отрезок». Значит ли это «не больше L за любые W секунд»? Посмотрите на первый пример: что происходит на границе отрезков?
2Подсказка 2
Ведро удобно вести в целых числах: вместо дробного числа токенов храните момент, когда ведро снова стало бы полным.
3Идея
Окно по часам — счётчик и номер текущего отрезка t div W. Ведро — алгоритм GCRA: пусть I = W/L и tat — время, когда ведро было бы полным; событие в момент t проходит, если t ≥ tat − (L − 1)·I, и тогда tat ← max(tat, t) + I. Самые насыщенные W секунд среди прошедших — двумя указателями: для каждого прошедшего события сдвигаем левый указатель, пока он отстаёт больше чем на W − 1 секунду.
4Разбор
Почему GCRA — это ведро. Число токенов в момент t — это L − (tat − t)/I, если tat > t, и L иначе: каждое прошедшее событие сдвигает «время полного ведра» на один интервал вперёд. Целый токен есть, когда tat − t ≤ (L − 1)·I. Сетевые устройства считают ведро именно так — без дробей и без таймера.
В первом примере L = 2, W = 10: события в 8 и 9 секунд проходят в первом отрезке, в 10 и 11 — во втором, и все четыре укладываются в отрезок [8, 18) — вдвое больше лимита. Это не ошибка реализации, а свойство способа: в худшем случае окно по часам пропускает 2L за W секунд. Ведро тоже не держит «L за любые W секунд»: оно отдаёт запас из L токенов сразу и ещё L за следующие W секунд. Разница в том, что у ведра это и есть обещание: за любые T секунд проходит не больше L + T/I, — подробнее в статье об ограничении частоты. На всплеске июля 2025 года окно по часам пропускает до 19 уведомлений за час при лимите 10.
4+Решение
5Сложность
O(n) на оба способа и на поиск самых насыщенных W секунд.
6Типичные ошибки
- Самые насыщенные W секунд — это самый насыщенный отрезок по часам. Нет: граница отрезка их разрезает. Первый пример.
- Дробные токены в числах с плавающей точкой. Сработает, но на совпадающих моментах и долгих потоках накопится ошибка; целые числа надёжнее.
- Ведро, которое начинается пустым. По условию вначале оно полное.
- Окно [t − W, t] вместо [s, s + W). События ровно через W секунд в одно окно не попадают.
Алгоритмы задачи
O(1) на запрос (журнал — O(N))
2 задачи
TEC
Приём
Два указателя
Два индекса движутся только вперёд и заменяют перебор пар или отрезков одним проходом за O(n).
O(n)
2 задачи