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

Запас ведра

ограничение нагрузки потоковая обработка жадность сети

Подписчик согласен получать не больше одного уведомления в I секунд в среднем, но готов к всплескам: ограничитель — ведро с токенами, которое пополняется на один токен каждые I секунд и вначале полное. Каждое уведомление забирает целый токен; если токена нет, уведомление теряется. Какое наименьшее ведро нужно, чтобы за весь поток не потерялось ни одного уведомления?

Среди тестов — все землетрясения магнитудой 5 и больше за 2015–2025 годы при одном, пяти, двадцати и шестидесяти уведомлениях в час.

Вход

В первой строке число потоков q (1 ≤ q ≤ 10). Для каждого — строка с n и I (1 ≤ n ≤ 2·10⁵, 1 ≤ I ≤ 10⁶) и строка с моментами уведомлений в секундах по неубыванию (целые от 0 до 10⁹). Сумма n не больше 3·10⁵.

Выход

Для каждого потока — наименьший размер ведра (целое число токенов).

Примеры

Пример 1

Вход

2
5 10
0 1 2 30 31
3 60
0 0 0

Выход

3
3

Пример 2

Вход

2
4 5
0 5 10 15
10 5
0 1 2 3 4 5 6 7 8 9

Выход

1
9

Ограничения

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

Разбор

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

1Подсказка 1

Возьмите любые подряд идущие уведомления с i-го по j-е. Сколько токенов им нужно и сколько ведро может им дать?

2Подсказка 2

Неравенство «нужно ≤ можно» для всех пар i ≤ j переписывается как разность двух чисел, одно из которых зависит только от i, другое — только от j. Наибольшая такая разность ищется за один проход.

3Идея

Уведомлениям с i-го по j-е нужно j − i + 1 токенов. Ведро размера b может дать за это время не больше b (запас к моменту t_i) плюс (t_j − t_i)/I (пополнение). Всё проходит ровно тогда, когда для всех i ≤ j: j − i + 1 ≤ b + (t_j − t_i)/I. Обозначим a_j = I·j − t_j; тогда условие — b ≥ (a_j − a_i)/I + 1. Ответ — ⌈D/I⌉ + 1, где D — наибольшая разность a_j − a_i при i ≤ j: бегущий минимум a и один проход.

4Разбор

Почему «достаточно» тоже верно, а не только «необходимо». Пусть условие выполнено, но какое-то уведомление j потерялось — первое такое. Найдём последний момент перед ним, когда ведро было полным, и первое уведомление i после этого момента. С тех пор ведро ни разу не переполнялось, значит, получило ровно b + (t_j − t_i)/I токенов, а потратило j − i — и всё же не хватило на j-е. Значит, j − i + 1 > b + (t_j − t_i)/I, противоречие.

Во втором примере десять уведомлений за десять секунд при токене раз в пять секунд: ведро должно быть на 9. Самый частый ошибочный ответ — «сколько уведомлений бывает за I секунд», здесь 5, — забывает, что всплеск длиннее одного интервала опустошает ведро постепенно. На каталоге землетрясений при пяти уведомлениях в час нужно ведро на 74: столько потребовал всплеск после землетрясения магнитудой 8,8 в июле 2025 года: 105 событий за шесть с небольшим часов, хотя за любой отдельный час — не больше 38. Подробнее о ведре и его гарантии — в статье об ограничении частоты.

4+Решение

5Сложность

O(n) на поток: один проход с бегущим минимумом.

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

Наибольшее число уведомлений за I секунд. Не учитывает длинные всплески: второй пример.
Перебор всех пар i ≤ j. O(n²) — десятки миллиардов пар на каталоге.
Округление. b ≥ D/I + 1 при нецелом D/I округляется вверх: ⌈D/I⌉ + 1.
Совпадающие моменты. Несколько уведомлений в одну секунду требуют по токену каждое — формула это учитывает, а «по одному в секунду» — нет.

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

SYS Алгоритм Ограничение частоты запросов Не больше N запросов в единицу времени: окно, журнал, два счётчика и ведро с токенами. O(1) на запрос (журнал — O(N)) 2 задачи TEC Приём Префиксные суммы Сумма любого отрезка за O(1) после одного прохода; двумерный вариант считает сумму любого прямоугольника картинки. O(n) на построение, O(1) на запрос 2 задачи