N дубов высажены в ряду на аллее перед зданием министерства обороны. Планируется срубить некоторые деревья, чтобы
N дубов высажены в ряду на аллее перед зданием министерства обороны. Планируется срубить некоторые деревья, чтобы придать аллее более воинственный вид, перед приездом главнокомандующего. В соответствии с внутренними правилами министерства, дуб может быть срублен только в двух случаях: * если и ближайший дуб слева, и ближайший дуб справа находятся ниже, чем данный дуб; * если и ближайший дуб слева, и ближайший дуб справа находятся выше, чем данный дуб. Крайние левый и крайний правый дуб не могут быть срублены в соответствии с этим правилом. Министр хочет разработать план рубки, который позволит
Блестящий_Тролль_5205 15
сделает аллею максимально воинственной. Для этого необходимо определить, сколько деревьев можно срубить в соответствии с правилами министерства.Для решения задачи, посмотрим на каждое дерево в ряду и проверим, выполняются ли условия срубления.
Пусть у нас есть N дубов в ряду. Создадим список HEIGHTS, содержащий высоту каждого дерева.
Затем мы должны выполнить следующие шаги:
1. Инициализировать переменную count = 0, которая будет содержать количество деревьев, которые можно срубить.
2. Циклически перебрать каждое дерево в ряду, начиная со второго и заканчивая предпоследним (поскольку крайние деревья не могут быть срублены).
3. Проверить условия срубления для текущего дерева:
- Если и ближайший дуб слева, и ближайший дуб справа находятся ниже, чем текущий дуб, увеличить count на 1.
- Если и ближайший дуб слева, и ближайший дуб справа находятся выше, чем текущий дуб, увеличить count на 1.
- В противном случае, перейти к следующему дереву в ряду.
4. Вывести количество деревьев, которые можно срубить (значение переменной count).
Давайте рассмотрим пример для лучшего понимания:
Пусть у нас есть N = 6 дубов, и высоты деревьев заданы следующим образом: HEIGHTS = [3, 2, 4, 5, 2, 1].
1. Изначально, count = 0.
2. Рассмотрим первое дерево высотой 2. Поскольку оно является крайним левым деревом, оно не может быть срублено.
3. Рассмотрим второе дерево высотой 4. Поскольку оно является вторым в ряду и оба ближайших дуба (высоты 3 и 2) ниже по высоте, увеличиваем count на 1.
4. Рассмотрим третье дерево высотой 5. Оба ближайших дуба (высоты 4 и 2) выше по высоте, поэтому увеличиваем count на 1.
5. Рассмотрим четвертое дерево высотой 2. Оба ближайших дуба (высоты 5 и 2) ниже по высоте, поэтому увеличиваем count на 1.
6. Рассмотрим пятое дерево высотой 1. Поскольку оно является крайним правым деревом, оно не может быть срублено.
7. Выводим результат: count = 3.
Таким образом, в данном примере можно срубить 3 дерева.
Этот алгоритм можно применить к любому количеству деревьев N, просто замените значения HEIGHTS на соответствующие высоты деревьев.