C++ Срочно
Покраска забора
У Васи на даче длина забора составляет N метров. Часть забора необходимо покрасить. При обследовании забор был разбит на N участков длиной 1 метр, и для каждого участка было определено, нуждается ли он в покраске или нет.
После того как валик для покраски пропитывается в ведре краской, им можно окрасить не более L
метров подряд. В том числе можно перекрашивать и участки в этом не нуждающиеся.
Определите, за какое количество подобных операций (пропитать валик краской и перекрасить не более L
метров) можно обновить забор так, чтобы все нуждающиеся в покраске фрагменты оказались окрашены.
Формат входных данных
Первая строка входных данных содержит целое число L
( 0
) — максимальную длину фрагмента, который можно перекрасить за одно действие. Во второй строке входных данных записано целое число N
( 0
) — длина забора. Следующие N
строк содержат по одному числу, равному 0
или 1
. Число 1
обозначает, что соответствующий участок забора нуждается в покраске, число 0
— что участок в покраске не нуждается.
Формат выходных данных
Программа должна вывести одно целое число — минимальное количество описанных действий, которое необходимо для перекраски забора.
Замечание
В тесте из примера за первое действие можно, например, перекрасить второй метр забора, а за второе — с 5
-го по 7
-й метр.
Ввод
Вывод
3
8
0
1
0
0
1
0
1
0
2
Ограничения
Время выполнения: 5 секунд
Процессорное время: 1 секунда
Память: 256 MB
Ответы
Ответ:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int L, N;
cin >> L >> N;
vector<int> fence(N);
for (int i = 0; i < N; i++) {
cin >> fence[i];
}
vector<int> segments;
int currentSegmentLength = 0;
for (int i = 0; i < N; i++) {
if (fence[i] == 1) {
currentSegmentLength++;
} else {
if (currentSegmentLength > 0) {
segments.push_back(currentSegmentLength);
currentSegmentLength = 0;
}
}
}
if (currentSegmentLength > 0) {
segments.push_back(currentSegmentLength);
}
sort(segments.begin(), segments.end(), greater<int>());
int numPaints = 0;
int i = 0;
while (i < segments.size()) {
int j = i;
int totalLength = 0;
while (j < segments.size() && totalLength + segments[j] <= L) {
totalLength += segments[j];
j++;
}
if (j == i) { // we cannot paint any segment
cout << "-1" << endl;
return 0;
}
numPaints++;
i = j;
}
cout << numPaints << endl;
return 0;
}
Объяснение:
Сначала мы считываем из входных данных максимальную длину фрагмента, который можно перекрасить за один раз, и длину забора. Затем мы считываем последовательность 0 и 1, где 1 означает нужду в покраске, а 0 - отсутствие необходимости. Затем мы вычисляем длины всех непрерывных фрагментов забора, которые нужно покрасить, и сохраняем их в вектор segments. Далее мы сортируем этот вектор в