Решение: Минимальная сумма показаний
По каналу связи передаётся последовательность целых чисел — показания прибора. В течение $N$ минут прибор ежеминутно регистрирует значение силы тока и передаёт его на сервер. Определите три таких переданных числа, чтобы между моментами передачи любых двух из них прошло не менее $K$ минут, а сумма этих трёх чисел была минимально возможной. Даны два входных файла: файл A и файл B. В каждом файле в первой строке содержится натуральное число $K$, во второй — количество показаний $N$ ($1 \leqslant N \leqslant 10\,000\,000$, $N>K$), а далее записаны $N$ натуральных чисел, не превышающих $10\,000\,000$. Запишите два числа: сначала искомую величину для файла A, затем для файла B. Типовой пример имеет иллюстративный характер; для выполнения задания используются данные из прилагаемых файлов. Для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов.
Решение по шагам
5 шаговПеребор всех троек позиций имеет слишком большую сложность, поэтому состояния нужно обновлять при одном проходе по файлу.
$$O(N^3)$$Пусть $a_i$ — показание в момент $i$. Для каждой позиции поддерживаем минимальную сумму одного, двух и трёх выбранных показаний, причём последние выбранные позиции удовлетворяют ограничению по расстоянию.
$$d_1(i)=a_i$$Перед обработкой позиции $i$ в структуру минимумов добавляются состояния позиций, которые уже находятся не ближе чем на $K$ минут. Минимум таких состояний используется для построения суммы двух чисел.
$$d_2(i)=a_i+\min_{j\leq i-K}d_1(j)$$Аналогично строится сумма трёх чисел: к текущему показанию прибавляется минимальная допустимая сумма двух показаний.
$$d_3(i)=a_i+\min_{j\leq i-K}d_2(j)$$Минимум всех рассчитанных значений $d_3(i)$ является искомой суммой. Алгоритм выполняется за линейное время и использует постоянный объём памяти, если хранить только необходимые минимумы и очередь отложенных состояний.
$$O(N)\text{ по времени},\quad O(N)\text{ или }O(K)\text{ по памяти}$$Численные ответы для файлов A и B нельзя определить без содержимого прилагаемых файлов.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Проверяют расстояние только между соседними выбранными позициями, хотя оно должно быть не менее $K$ между любыми двумя.
Используют перебор всех троек позиций.
Добавляют позицию в минимум раньше, чем она становится допустимой по ограничению $K$.
Путают номер позиции и количество минут между моментами передачи.