Задание №168134: Задание 5

Задача 5. Хлеб и зрелище
В этой задаче в данном массиве из n элементов нужно найти два отрезка длины t каждый с
минимальной общей суммой, при этом между отрезками должен быть хотя бы один элемент, не
принадлежащий этим отрезкам.
Самая простая идея — перебрать начала двух отрезков. Если индекс первого элемента левого

отрезка равен i, то правый отрезок может иметь начальным элементом отрезок с индексом j = i+t+1
или больше, начиная с этого значения и будем перебирать j. Дальше посчитаем суммы элементов
на данных отрезках и выберем из них наименьшее. Такое решение будет иметь сложность O(n2t).
n = int (input ())
t = int (input ())
d = [ int (input ()) for i in range(n )]

Страница 3 из 5

Пригласительный этап всероcсийской олимпиады по информатике для 8–10 классов
29-30 мая 2025
ans = 10∗∗9
i = 0

while i + 2 ∗ t + 1 <= n:
j = i + t + 1
while j + t <= n:
ans = min(ans , sum(d[ i : i+t ]) + sum(d[ j : j+t ] ) )
j += 1
i += 1
print ( ans )

Это решение можно улучшить при помощи стандартного приёма: предподсчитаем значения каж-
дой нужной нам суммы. Пусть sums[i] будет равно сумме элементов массива d, начиная с i-го эле-
мента. Один раз вычислим эти суммы, чтобы впоследствии не считать их заново. Сами эти суммы
легко посчитать при помощи техники «скользящего окна»: если мы посчитали сумму элементов от
d[i] до d[i+t−1], то чтобы перейти к следующей сумме нужно добавить значение d[i+t] и вычесть
значение d[i].
Такое решение будет иметь сложность O(n2).
n = int (input ())
t = int (input ())
d = [ int (input ()) for i in range(n )]
sums = [ 0 ] ∗ (n − t + 1)

sums [ 0 ] = sum(d [ 0 : t ])
for i in range(0 , n − t ):
sums [ i +1] = sums [ i ] + d[ i+t ] − d[ i ]
ans = 10∗∗9
i = 0
while i + 2 ∗ t + 1 <= n:
j = i + t + 1
while j + t <= n:
ans = min(ans , sums [ i ] + sums [ j ])
j += 1
i += 1
print ( ans )

Наконец, чтобы улучшить и это решение, можно заметить, что если мы выбрали какой-то ответ,
то первый отрезок можно двигать на некотором префиксе нашего массива, а второй отрезок — на
некотором суффиксе. То есть задача сводится к тому, что мы должны выбирать наименьшее значе-
ние среди значений массива sums на некотором его префиксе или суффиксе. Это можно сделать при
помощи стандартной техники префиксных минимумов — предподсчитаем минимумы на всех пре-
фиксах и всех суффиксах массива. Это можно сделать за O(n). Дальше можно, например, перебрать
ту минуту, которую Петя обязательно проведёт в магазине. Нужно рассмотреть префиксы массива,
не включающие эту минуту, и выбрать на этом префиксе отрезок из t элементов с минимальной
суммой. Затем нужно рассмотреть суффиксы, не включающие эту минуту, и выбрать на этом суф-
фиксе отрезок длины t с минимальной суммой. Используя массивы префиксных и суффиксных
минимумов, это можно сделать за O(1), и общее решение будет иметь сложность O(n).
У этой идеи есть разные варианты, например, рассмотрим решение, вообще не использующее
вспомогательные массивы. В этом решении мы будем перебирать индекс j начала правого отрезка. А
значение i будет равно максимальному возможному началу левого отрезка, на самом деле i=j−t−1,
но для простоты будем использовать две переменные. Переменная sum1 будет равна сумме отрезка
длины t, начиная с индекса i, а переменная sum2 будет равна сумме отрезка длины t, начиная с
индекса j.

При увеличении i и j на 1 переменные sum1 и sum2 пересчитываются добавлением одного и
вычитанием другого элемента массива.

Страница 4 из 5

Пригласительный этап всероcсийской олимпиады по информатике для 8–10 классов
29-30 мая 2025
При фиксированном значении j в качестве начала левого отрезка можно взять любое значение,
не превосходящее i, поэтому для фиксированного j наилучшая сумма, которую можно взять, равна
sum2 и наименьшему из значений sum1, которые возникали до этого. Поэтому будем хранить в

переменной min_sum1 наименьшее из значений sum1, пересчитывая его каждый раз при сдвиге i.
Такое решение имеет сложность O(n).
n = int (input ())
t = int (input ())
d = [ int (input ()) for i in range(n )]
i = 0
j = t + 1
sum1 = sum(d[ i : i+t ])
sum2 = sum(d[ j : j+t ])
min_sum1 = sum1
ans = sum1 + sum2

while j + t < n:
sum1 += d[ i+t ]
sum1 −= d[ i ]
min_sum1 = min(min_sum1, sum1)
i += 1
sum2 += d[ j+t ]
sum2 −= d[ j ]
j += 1
ans = min(ans , min_sum1 + sum2)
print ( ans )

Страница 5 из 5