Форум программистов, компьютерный форум 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) удалить из слова первую... подробнее

Показать сообщение отдельно
notAll
395 / 116 / 23
Регистрация: 27.05.2016
Сообщений: 302
Завершенные тесты: 2
07.07.2016, 11:22
Тогда так:
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
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
 
template <typename It>
bool check(It first, It last)
{
    auto it = std::is_sorted_until(first, last);
    if (it != last)
    {
        //1 - delete first broken element
        It prev, next;
        prev = next = it;
        if (*--prev < *++next)
            return std::is_sorted_until(next, last) == last;
 
        //2 - delete prev element before broken
        prev = it;
        if ((prev - first) > 1 && *----prev < *it)
            return std::is_sorted_until(next, last) == last;
        else if ((prev - first) == 1)
            return std::is_sorted_until(it, last) == last;
 
        return false;
    }
 
    return true;
}
 
template <typename T>
void print(const std::vector<T> &v)
{
    for (const auto &i : v)
        std::cout << i << ", ";
}
 
int main()
{
    std::vector<std::vector<int>> vec {
        {1,2,3,4,5}, //true
        {1,2,3,4,5,0}, //true
        {1,2,3,4,0,5}, //true
        {42,1,2,3,4,5}, //true
        {1,42,2,3,4,5}, //true
        {42,1,2,3,4,5,0}, //false
        {1,42,2,3,4,42,5}, //false
        {1,1,0,0,1,1}, //false
        {3,4,1,2} //false
    };
 
    std::cout << std::boolalpha;
    for (auto &v : vec) {
        print(v);
        std::cout << " - " << check(std::begin(v), std::end(v)) << "\n";
    }
}
Добавлено через 11 минут
И с проверкой на обратную сортировку:
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
#include <iostream>
#include <vector>
#include <functional>
#include <iterator>
#include <algorithm>
 
template <typename It, typename Comparator =
          std::less<typename std::iterator_traits<It>::value_type>>
bool check_impl(It first, It last, Comparator comp = Comparator())
{
    auto it = std::is_sorted_until(first, last, comp);
    if (it != last)
    {
        //1 - delete first broken element
        It prev, next;
        prev = next = it;
        if (comp(*--prev, *++next))
            return std::is_sorted_until(next, last, comp) == last;
 
        //2 - delete prev element before broken
        prev = it;
        if ((prev - first) > 1 && comp(*----prev, *it))
            return std::is_sorted_until(next, last, comp) == last;
        else if ((prev - first) == 1)
            return std::is_sorted_until(it, last, comp) == last;
 
        return false;
    }
 
    return true;
}
 
template <typename It>
bool check(It first, It last)
{
    if (!check_impl(first, last))
        return check_impl(first, last,
                          std::greater<typename std::iterator_traits<It>::value_type>());
    return true;
}
 
template <typename T>
void print(const std::vector<T> &v)
{
    for (const auto &i : v)
        std::cout << i << ", ";
}
 
int main()
{
    std::vector<std::vector<int>> vec {
        {1,2,3,4,5}, //true
        {1,2,3,4,5,0}, //true
        {1,2,3,4,0,5}, //true
        {42,1,2,3,4,5}, //true
        {1,42,2,3,4,5}, //true
        {42,1,2,3,4,5,0}, //false
        {1,42,2,3,4,42,5}, //false
        {1,1,0,0,1,1}, //false
        {3,4,1,2} //false
    };
 
    std::cout << std::boolalpha;
    for (auto &v : vec) {
        print(v);
        std::cout << " - " << check(std::begin(v), std::end(v)) << "\n";
    }
}
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru