Числовая последовательность называется пилообразной если каждый ее член (кроме первого и последнего) либо больше обоих своих соседей, либо меньше обоих соседей. Например, последовательность 1, 2, 1, 3, 2 является пилообразной, а 1, 2, 3, 1, 2 — нет, поскольку 1 < 2 < 3. Любая последовательность из одного элемента является пилообразной. Последовательность из двух элементов является пилообразной, если ее элементы не равны.
Дана последовательность. Требуется определить, какое наименьшее количество ее членов нужно вычеркнуть, чтобы оставшаяся последовательность оказалась пилообразной.
Входные данныеЖ В первой строке входного файла записано одно число N (1≤N≤100000) — количество членов последовательности. Во второй строке записано N натуральных чисел, не превосходящих 10 000 — члены последовательности.
Выходные данные: в выходной файл выведите одно число — минимальное количество членов, которые необходимо вычеркнуть.
#include <iostream>
#include <vector>
using namespace std;
int main()
{
//делаем ввод
int N;
int b = 0;
cin >> N;
vector<int> pila;
for (int i = 0; i < N; i++){
int a;
cin >> a;
pila.push_back(a);
}
//пишем, сколько раз нужно проверять
for (int i = 0; i <= b + 1; i++){
//проверяем
for (int j = 1; j < N - 1; j++){
if ((pila.at(j - 1) < pila.at(j) && pila.at(j) < pila.at(j + 1)) || (pila.at(j - 1) > pila.at(j) && pila.at(j) > pila.at(j + 1))){
pila.erase(pila.begin() + j - 1);
b++;
}
}
}
//ещё проверяем
if (pila.size() == 2){
if (pila.at(0) == pila.at(1)){
pila.erase(pila.begin());
}
}
//выводим
cout << b << endl;
return 0;
}
Ну вы же удаляете из вектора элементы:
pila.erase(pila.begin() + j - 1);
но при этом все равно работаете до индекса N-2
.
for (int j = 1; j < N - 1; j++){
А там уже вполне может не быть столько элементов, правда?
P.S. Правильность алгоритма не рассматривал.
Кофе для программистов: как напиток влияет на продуктивность кодеров?
Рекламные вывески: как привлечь внимание и увеличить продажи
Стратегії та тренди в SMM - Технології, що формують майбутнє сьогодні
Выделенный сервер, что это, для чего нужен и какие характеристики важны?
Современные решения для бизнеса: как облачные и виртуальные технологии меняют рынок
Установка пустого атрибута ACCESS_EXTERNAL_DTD вызывает исключение "не поддерживается: http://javaxxml
Получилось синхронизировать состояние бокового меню с кнопкой бургера через ActionBarDrawerToggleТ
На интервью задали такую задачу: дан массив длиной n, необходимо реализовать методы добавления элемента и обнуление(значения всех элементов...
Создал проект с шаблоном Bottom Navigation ActivityФрагменты, которые входят в нижнее меню, плавно сменяют друг друга