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

Сушь

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

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

Второй и третий тесты — осадки Алматы по дням за 1941–2025 годы (реанализ ERA5 через Open-Meteo), в десятых долях миллиметра: 31 046 дней.

Вход

В первой строке n и q (1 ≤ n ≤ 2·10⁵, 1 ≤ q ≤ 10). Во второй — n целых чисел от 0 до 10⁶, в третьей — q пределов S от 0 до 2·10¹¹.

Выход

Для каждого предела — длина самого длинного периода; 0, если даже один день превышает предел.

Примеры

Пример 1

Вход

10 4
5 0 0 12 0 3 0 0 0 9
0 3 5 100

Выход

Ограничения

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

Разбор

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

1Подсказка 1

Осадки не бывают отрицательными. Что это значит для суммы окна, когда его левый край сдвигается вправо?

2Идея

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

3Разбор

Каждый указатель проходит ряд один раз, на предел уходит O(n), на все — O(n·q). Можно и иначе: с префиксными суммами и двоичным поиском для каждого правого края искать самый левый подходящий — O(n log n) на предел. Это решение годится и тогда, когда два указателя не работают.

А когда они не работают? Если в ряду бывают отрицательные числа, сдвиг левого края может увеличить сумму, и «догонять» нельзя. Тогда помогают только префиксные суммы.

Суммы доходят до 2·10¹¹ — в Go нужен int64.

3+Решение

4Сложность

O(n) на один предел, O(n·q) на все.

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

Перебор начал. Для каждого дня растить окно, пока влезает, — O(n·L), а при больших пределах окна длинные.
Предел меньше одного дня. Если даже один день больше предела, ответ 0, а левый указатель уходит правее правого — проверьте, что код это переживает.
32-битная сумма. В шестом тесте сумма всех дней — 2·10¹¹.

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

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