Основные подходы к решению.
- Перебор всех троек L, M, R таких, что \(M-L\geq K \ и\ R-M\geq K\)
вычисление суммы \(x=A_L+A_M+A_R\), сравнение x с ответом
(Ai - показание прибора на i-ой минуте)
Сложность такого алгоритма O(N3)
- Нетрудно заметить, что если выполняется условие расстояния для пар L,M и M,R, то
автоматически выполняется условие для пары L,R.
Oпределим FM, положив: \(F_M=min(A_0,\cdots,A_{M-K})+A_M+min(A_{M+K}\cdots+A_{N-1})\)
Тогда ответом на задание будет \(x = min(F_M | M=K,\cdots,N-1-K)\)
Для вычисления x можно воспользоваться следующим алгоритмом:
- построить список из \(B_j=min(A_0,\cdots,A_j)+A_{j+k}\) ( фактически, \(min(B_0,\cdots B_{N-1-K}) \)
было бы решение для задачи с парой показаний)
- построить список из \(D_i=min(B_0,\cdots,B_i)+A_{i+2\cdot K}\)
Значение \(y = min(D_0,\cdots D_{N-1-2\cdot K}) \) и будет ответом на задачу
Сложность вычисления списка из Bj составляет O(N) (фактически создается стек с поддержкойй)
Построение списка из Di аналогично построению списка из Bj и тоже будет иметь линейную сложность.
Организация решения по слоссобу I никакой сложности не имеет, поэтому опишем решение задания по способу II,
причем в общем случае (будем считать, что набор состояний может состоять из t значений)