В некоторых случаях программа ничего не выводит. Почему?

Question

Задача "Наибольшая пилообразная подпоследовательность"

Числовая последовательность называется пилообразной если каждый ее член (кроме первого и последнего) либо больше обоих своих соседей, либо меньше обоих соседей. Например, последовательность 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++){
        //проверка

        //если все члены вектора равны
        int c = 0;
        for (int j = 1; j < N - b; j++){
            if (pila.at(j) == pila.at(j - 1)){
                c++;
            }
        }

        if (c == N - b - 1){
            b = N - 1;
            break;
        }

        //иначе
        else{
            for (int j = 1; j < N - b - 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);
                    b++;
                }
            }
        }
    }

    //вывод
    cout << b << endl;
    return 0;
}

Answer 1

В данном случае я использовал заполнение через генерацию. Вам нужно заменить генерацию на ввод.

При добавлении нового элемента в вектор, мы проверяем не равен ли он предыдущему. Если равен, то нам надо будет его в дальнейшем удалить. Если не равен, то уже смотрим, основываясь на flag, каким он должен быть - меньше или больше предыдущего, затем меняем flag в противоположную сторону

#include <iostream>
#include <random>
#include <vector>

using namespace std;
int main()
{
    bool flag = false;
    vector<int> pila;
    random_device rd;
    default_random_engine gen(rd());
    uniform_int_distribution<> dis(
        1,   
        10000);
    size_t N, cCnt(0);

    N = 10000;

    pila.push_back(dis(gen));
    for (int i = 1; i < N; i++) {
        pila.push_back(dis(gen));
        if (pila.at(i) == pila.at(i - 1)) ++cCnt;
        else if (pila.at(i) < pila.at(i - 1)) {
            if (!flag) ++cCnt; else flag = false;
        }
        else {
            if (flag) ++cCnt; else flag = true;
        };
    }
    cout << cCnt;
    return 0;
}

БЛОГ НА HUSL

В некоторых случаях программа ничего не выводит. Почему?

Ответы (1 шт):