Числовая последовательность называется пилообразной если каждый ее член (кроме первого и последнего) либо больше обоих своих соседей, либо меньше обоих соседей. Например, последовательность 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. Правильность алгоритма не рассматривал.
Айфон мало держит заряд, разбираемся с проблемой вместе с AppLab
Установка пустого атрибута ACCESS_EXTERNAL_DTD вызывает исключение "не поддерживается: http://javaxxml
Получилось синхронизировать состояние бокового меню с кнопкой бургера через ActionBarDrawerToggleТ
На интервью задали такую задачу: дан массив длиной n, необходимо реализовать методы добавления элемента и обнуление(значения всех элементов...
Создал проект с шаблоном Bottom Navigation ActivityФрагменты, которые входят в нижнее меню, плавно сменяют друг друга