Тестирование Сириус c++
Покраска забора
У Васи на даче длина забора составляет N метров. Часть забора необходимо покрасить. При обследовании забор был разбит на N участков длиной 1 метр, и для каждого участка было определено, нуждается ли он в покраске или нет.
После того как валик для покраски пропитывается в ведре краской, им можно окрасить не более L
метров подряд. В том числе можно перекрашивать и участки в этом не нуждающиеся.
Определите, за какое количество подобных операций (пропитать валик краской и перекрасить не более L
метров) можно обновить забор так, чтобы все нуждающиеся в покраске фрагменты оказались окрашены.
Формат входных данных
Первая строка входных данных содержит целое число L
( 0<L≤ 100000
) — максимальную длину фрагмента, который можно перекрасить за одно действие. Во второй строке входных данных записано целое число N
( 0<N< 100000
) — длина забора. Следующие N
строк содержат по одному числу, равному 0
или 1
. Число 1
обозначает, что соответствующий участок забора нуждается в покраске, число 0
— что участок в покраске не нуждается.
Формат выходных данных
Программа должна вывести одно целое число — минимальное количество описанных действий, которое необходимо для перекраски забора.
Замечание
В тесте из примера за первое действие можно, например, перекрасить второй метр забора, а за второе — с 5
-го по 7
-й метр.
Для решения задачи можно использовать жадный алгоритм:
Идем по всем участкам забора слева направо.
Если текущий участок нуждается в покраске, то:
Если предыдущий участок тоже нуждается в покраске, то продолжаем красить текущий участок вместе с предыдущим, пока не достигнем максимальной длины, которую можно покрасить за одно действие (L).
Если предыдущий участок не нуждается в покраске или мы достигли максимальной длины для текущего действия, то завершаем текущее действие и начинаем новое.
Повторяем шаги 2-3 до тех пор, пока не покрасим все нуждающиеся в покраске участки забора.
После завершения алгоритма количество завершенных действий будет являться ответом на задачу.
Вот реализация на C++:
#include <iostream>
using namespace std;
int main() {
int L, N;
cin >> L >> N;
int painted = 0; // количество уже покрашенных участков
int actions = 0; // количество выполненных действий
int prev_painted = 0; // длина последовательности покрашенных участков в предыдущем действии
for (int i = 0; i < N; i++) {
int segment;
cin >> segment;
if (segment == 1) {
painted++;
if (painted - prev_painted == L || painted == N) {
// текущая последовательность участков достигла максимальной длины
// или это последний участок в заборе, завершаем текущее действие
actions++;
prev_painted = painted;
}
} else {
// текущий участок не нуждается в покраске, завершаем текущее действие
if (painted - prev_painted > 0) {
actions++;
prev_painted = painted;
}
}
}
cout << actions << endl;
return 0;
}