Решение: Максимальная сумма осадков
По каналу связи передаётся последовательность целых неотрицательных чисел — показания прибора, полученные с интервалом в 1 мин. в течение $T$ мин. Прибор измеряет количество атмосферных осадков, полученное регистратором за минуту, предшествующую моменту регистрации, и передаёт это значение в условных единицах измерения.
Определите два таких переданных числа, чтобы между моментами их передачи прошло не менее $K$ мин., а их сумма была максимально возможной. Укажите найденное суммарное количество осадков.
Даны два входных файла — файл A и файл B. В первой строке каждого файла содержится натуральное число $K$ — количество минут, которое должно пройти между двумя передачами показаний, во второй — количество переданных показаний $N$ ($1 \leq N \leq 10\,000\,000$, $N > K$). В каждой из следующих $N$ строк находится одно целое неотрицательное число, не превышающее $100\,000$, обозначающее количество осадков за соответствующую минуту.
Для обработки файла B нельзя использовать переборный алгоритм, вычисляющий сумму для всех возможных пар.
Запишите два числа: сначала значение искомой величины для файла A, затем — для файла B. В типовом примере при $K=3$ и последовательности $15, 10, 200, 0, 30$ максимальная сумма равна $45$.
Решение по шагам
4 шагаДва показания с индексами $i$ и $j$ допустимы, если расстояние между моментами их передачи не меньше $K$, то есть $|i-j| \geq K$.
При просмотре последовательности слева направо для элемента с индексом $i$ достаточно знать максимальный элемент среди позиций от $1$ до $i-K$. Этот максимум можно поддерживать за постоянное время на каждом шаге.
Для каждого текущего значения вычисляем сумму с сохранённым максимумом допустимой предыдущей части последовательности и обновляем глобальный максимум.
Алгоритм работает за $O(N)$ времени и использует $O(1)$ дополнительной памяти, если обрабатывать файл потоково и хранить очередь или необходимые отложенные значения.
Два числовых значения, вычисляемые по данным файлов A и B.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Проверяют только соседние элементы или пары с расстоянием ровно $K$.
Используют перебор всех пар, что имеет сложность $O(N^2)$ и неприемлемо для файла B.
Путают условие «не менее $K$ минут» с условием «не более $K$ минут».
Забывают вывести сначала результат для файла A, затем результат для файла B.