Автор задачи и разработчик: Александр Гордеев
При внимательном рассмотрении условия можно заметить, что эту задачу можно свести к другой — заполнить плоскость, которая была образована кальмарами, минимальным числом прямоугольников.
Решим для начала более простую задачу — пусть наши прямоугольники имеют высоту $$$1$$$. Тогда в начале нужно «открыть» $$$a_1$$$ отрезков, при переходе к $$$a_2$$$ либо открыть ещё $$$a_2 - a_1$$$ отрезков, если $$$a_2 > a_1$$$ и закрыть $$$a_1 - a_2$$$ отрезков в противном случае и новые отрезки не появляются. Тогда ответ на задачу — сумма разностей соседних значений $$$a_{i + 1} - a_i$$$, если эта разность больше нуля.
Попробуем применить аналогичную логику к этой задаче — в $$$a_1$$$ достаточно открыть один прямоугольник с началом в столбце $$$1$$$ и изначальной высотой $$$a_1$$$. Конец же этого прямоугольника мы выберем позже. Теперь перейдём на столбец $$$2$$$. Если $$$a_2 > a_1$$$, то достаточно создать ещё один прямоугольник с началом в $$$2$$$ и высотой $$$a_2 - a_1$$$. Но что если $$$a_1 > a_2$$$?
Заведём стек, в который будем добавлять наши открытые, но ещё не закрытые прямоугольники. Тогда при $$$a_{i + 1} > a_i$$$ мы бы добавили в стек число, равное $$$a_{i+1} - a_i$$$. Если $$$a_{i + 1} < a_i$$$, то нужно как-то уменьшить высоту, на которой мы сейчас находимся. Пользуемся тем, что прямоугольники добавляются в порядке появления, значит числа в стеке будут лежать в том же порядке, что и соответствующие прямоугольнике на гистограмме, и сверху стека будет лежать самый верхний незакрытый прямоугольник. Тогда достаточно убрать столько чисел со стека, чтобы их сумма была равна разнице:
Но возникает проблема — а что делать если сумма верхних элементов не может быть в точности равна $$$a_i$$$?
Если мы уберём прямоугольник высоты $$$1$$$, то следующий столбец будет высоты $$$4 \neq 2$$$, если $$$1$$$ и $$$3$$$, то следующий столбец будет высоты $$$1$$$, что тоже не подойдёт. Поступим так — сверху будем убирать числа пока можем, если же со следующим удаляемым сумма превысит разность соседних столбцов (обозначим непокрытый остаток разницы как $$$diff$$$), то тогда достаточно разбить «слишком большой» удаляемый $$$x$$$ на два прямоугольника — $$$diff$$$ и $$$x - diff$$$. Тогда убираем прямоугольник высоты $$$diff$$$ и тогда проблема решена.
Так получаем жадный алгоритм решения. В начале добавляем в стек натуральное число $$$a_1$$$. Если $$$a_i > a_{i - 1}$$$, то добавляем в стек $$$a_i - a_{i - 1}$$$. Иначе убираем числа с верхушки стека, пока их сумма не будет равна $$$a_{i - 1} - a_i$$$. Если не получается убрать со стека элементы ровно с этой суммой, то одно из чисел $$$x$$$ бьём на два, равные $$$diff$$$ и $$$x - diff$$$. Ответ — количество добавленных в стек чисел. Важно также заметить, что нули, добавленные в стек, в ответ не идут по очевидным причинам.