Форум программистов, компьютерный форум CyberForum.ru

Определение возможности сортировки массива удалением одного элемента - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Исполнение функции-члена в отдельном потоке http://www.cyberforum.ru/cpp-beginners/thread1773562.html
Здравствуйте, форум! Вот такой вот пример: Имеется класс, в котором есть 3 перегрузки одной функции. class A { public: void func1();
C++ Обработка записей содержащих структуры "Студент" Задание для самостоятельного выполнения Составить программу, обеспечивающую формирование данных из задания 5 в виде списка. Реализовать следующие операции работы со списком в виде меню: Меню: 1.Добавление записи (подменю: 1.1. в начало списка, 1.2.в конец списка, 1.3.после первой записи, удовлетворяющей некоторому условию (придумать самостоятельно)) 2.Удаление записи (по значению текстового... http://www.cyberforum.ru/cpp-beginners/thread1773559.html
Обработка структур AER0FL0T C++
Описать структуру с именем AER0FL0T, содержащую следующие поля: • название пункта назначения рейса; • номер рейса; • тип самолета. •Вывести номера рейсов и типов самолетов,вылетающих в пункт назначения ,название которого совпало и с названием введенным с клавиатуры • если таких рейсов нет, вывести соответствующее сообщение).
Зеркально отразить элементы матрицы относительно горизонтальной оси симметрии C++
Дана квадратная матрица порядка . Зеркально отразить ее элементы относительно горизонтальной оси симметрии матрицы.
C++ Динамически распределяемая память, удаление символов в строке http://www.cyberforum.ru/cpp-beginners/thread1773513.html
Нужна помощь в написании программы: Удаление символов Написать функцию, обеспечивающую ввод с клавиатуры строки неограниченной длины без редактирования. Написать функцию, которая удаляет символы, стоящие между двумя определенными символами. Символ вводится пользователем. Примечание: В каждой задаче должна быть реализована проверка на целостность кучи. При работе со строками учитывать символ...
C++ Напечатать все слова последовательности, предварительно преобразовав каждое из них по правилу Нужна помощь в написании программы: Дана последовательность, содержащая до 5 слов, в каждом из которых до 5 строчных латинских букв; между соседними словами — не менее одного пробела, за последним словом — точка. Напечатать все слова последовательности, предварительно преобразовав каждое из них по следующему правилу: 1) перенести последнюю букву в начало слова; 2) удалить из слова первую... подробнее

Показать сообщение отдельно
Mr.X
Эксперт С++
3048 / 1693 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
07.07.2016, 18:25     Определение возможности сортировки массива удалением одного элемента
Цитата Сообщение от avgoor Посмотреть сообщение
Иначе рассматриваем подмассив из четырех элементов, где в середине меняется знак. Если знак меняется на границе массива - ответ "да". Иначе (рассматриваем для ясности пример с одним "-" он, напомню между, [1] и [2]) если [0]<=[1]<=[3] или [0]<=[2]<=[3] ответ "да". Для случая единственного "+" - аналогично. Если и + и - встречаются 1 раз - рассмотреть нужно оба.
Да-да, на самом деле достаточно проверить, что если аномальная разность не крайняя, то она не превосходит по модулю обе соседние.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
///////////////////////////////////////////////////////////////////////////////
//8.
///////////////////////////////////////////////////////////////////////////////
//На входе есть не менее 4 целых чисел, нужно определить, можно ли удалив
//не более одного элемента получить невозрастающий или неубывающий массив.
//Может кто-либо реализовать это, или дать описание наиболее быстрого способа?
///////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <iterator>
#include <vector>
///////////////////////////////////////////////////////////////////////////////
typedef std::vector     < int   >   T_numbers;
///////////////////////////////////////////////////////////////////////////////
T_numbers   make_rand_numbers()
{
    T_numbers   res{ 1, 2, 3, 4 };
 
    std::random_shuffle
        (
            res.begin   (),
            res.end     ()
        );
 
    return  res;
}
///////////////////////////////////////////////////////////////////////////////
bool    sequence_is_monotone_except_may_be_one_element( T_numbers    const   &   numbers )
{
    bool    bool_res    =   numbers.size()  <=  3;
 
    if( bool_res )
    {
        return  bool_res;
    }
 
    int     diff_prev           {};
    int     diff                {};
 
    int     count_pos           {};
    int     count_neg           {};
    int     count_min           {};
 
    int     pos_pos             {};
    int     pos_neg             {};
 
    int     bad_pos_adj_count   {};
    int     bad_neg_adj_count   {};
 
    for( size_t  i{1}; i < numbers.size(); ++i )
    {
        diff    =   numbers[i]
                -   numbers[i - 1];
 
        if  (
                    i                   ==  pos_pos     +   1
                &&  count_pos           ==  1
                &&  abs( diff_prev )    >   abs( diff )
            )
        {
            ++bad_pos_adj_count;
 
            if( bad_pos_adj_count   ==  2 )
            {
                ++count_pos;
            }
        }//if
 
        if  (
                    i                   ==  pos_neg     +   1
                &&  count_neg           ==  1
                &&  abs( diff_prev )    >   abs( diff )
            )
        {
            ++bad_neg_adj_count;
 
            if( bad_neg_adj_count   ==  2 )
            {
                ++count_neg;
            }
        }//if
 
        if( !diff )
        {
            continue;
        }
 
        if( diff    >   0 )
        {
            if( ++count_pos ==  1 )
            {
                pos_pos     =   i;
 
                if  (
                            i   >   1
 
                        &&      abs( diff       )
                            >   abs( diff_prev  )
                    )
                {
                    ++bad_pos_adj_count;
                }
            }//if
        }
        else
        {
            if( ++count_neg ==  1 )
            {
                pos_neg     =   i;
 
                if  (
                            i   >   1
 
                        &&      abs( diff       )
                            >   abs( diff_prev  )
                    )
                {
                    ++bad_neg_adj_count;
                }
            }//if
        }//else
 
        count_min   =   std::min    (
                                        count_pos,
                                        count_neg
                                    );
 
        bool_res    =       count_min
                        <=  1;
 
        if( !bool_res )
        {
            break;
        }
 
        diff_prev   =   diff;
    }//for
 
    return  bool_res;
}
///////////////////////////////////////////////////////////////////////////////
int     main()
{
    srand(unsigned(time(0)));
 
    for(;;)
    {
        auto    numbers     =   make_rand_numbers                               ();
        bool    bool_res    =   sequence_is_monotone_except_may_be_one_element  ( numbers );
 
        if( !bool_res )
        {
            std::copy
                (
                    numbers.begin               (),
                    numbers.end                 (),
                    std::ostream_iterator<int>  ( std::cout,    "\t" )
                );
 
            std::cout   <<  std::boolalpha
                        <<  bool_res
                        <<  std::endl;
 
            system("pause");
        }//if
    }//for
}
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru