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

Разместить флажки на прямой как можно дальше друг от друга - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Сформировать одномерный массив, каждый элемент которого равен сумме цифр элемента исходного массива http://www.cyberforum.ru/cpp-beginners/thread1778938.html
Ребята, помогите решить задачу Только перешел на массивы Сформировать одномерный массив, каждый элемент которого равен сумме цифр соответствующего элемента исходного массива, состоящего из целых десятичных положительных чисел. кто возмется, большое спасибо если что, начало должно заключаться в #include<iostream> #include<windows.h>
C++ Почему Compilation error? Дан некоторый набор букв и словарь. Ваша задача - подсчитать, сколько различных слов из словаря можно составить из этих букв. Входные данные В первой строке файла INPUT.TXT записано число N - количество слов в словаре (0 <= N <= 1000). В следующих N строках файла записано по одному слову из словаря. Слова содержат от 1 до 10 маленьких латинских букв. Все слова в словаре различны. В... http://www.cyberforum.ru/cpp-beginners/thread1778898.html
C++ Отобразить текущую дату
Народ помогите плиз,только начал с классами разбираться,как можно сделать? Нужно создать класс DataAndTime с конструктором, использующим текущее время, возвращаемое функцией time() ( time.h ) и дату, полученную функцией gmtime().
C++ Создание и размер динамических массивов
Имеется такая задача: Напишите фрагмент кода, который запрашивает у пользователя положительное целое число и затем создает динамический массив с указанным количеством элементов типа int. Сделайте это с применением операции new, а затем с использованием объекта vector. Сделал это так: #include "stdafx.h" #include <iostream> #include <array> #include <vector>
C++ Реализовать класс Student http://www.cyberforum.ru/cpp-beginners/thread1778856.html
есть класс нужно создать 3 динамических массива одномерных что бы элементы каждого из массивов вводились в мейне все начальные данные описаны и созданы в коде помогите правильно создать хотя бы 1 массив //1. Реализовать класс Student, который содержит поля для хранения фамилии, //имени, отчества, даты рождения, домашнего адреса, телефонного номера. //Также за каждым студентом...
C++ Ios_base::ate Здравствуйте, не могу понять, почему следующий код выводит в место 123456 просто 456. #include "stdafx.h" #include <iostream> #include <fstream> #include <string> using namespace std; int main() { ofstream a{ "1.txt",ios_base::ate }; подробнее

Показать сообщение отдельно
Mr.X
Эксперт С++
3048 / 1693 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
13.07.2016, 07:31     Разместить флажки на прямой как можно дальше друг от друга
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
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
///////////////////////////////////////////////////////////////////////////////
//5.
///////////////////////////////////////////////////////////////////////////////
//На прямой отмечены N точек, имеющих координаты X0, X1, ..., XN - 1.
//В этих точках нужно расставить M флажков, причём флажки нужно разместить
//как можно дальше друг от друга.
 
//Назовём критической дистанцией расстояние между двумя ближайшими соседними
//флажками. Требуется расставить флажки так, чтобы критическая дистанция
//была как можно больше.
 
//Определите максимальное возможное значение критической дистанции, которого
//можно достичь при расстановке флажков.
 
//Входные данные
//Первая строка содержит целые числа N и M (2 ≤ M ≤ N ≤ 10^5) —
//соответственно количество точек и количество флажков.
 
//Вторая строка содержит N упорядоченных по неубыванию целых чисел Xi
//( - 10^9 ≤ Xi ≤ 10^9) — координаты точек.
 
//Выходные данные
//Выведите одно целое число — максимально возможное значение критической дистанции.
 
//Примеры тестов
//входные данные
//5 2
//0 3 4 4 9
//выходные данные
//9
 
//входные данные
//5 3
//0 3 4 4 9
//выходные данные
//4
 
//входные данные
//5 3
//1 2 4 5 6
//выходные данные
//2
///////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <iostream>
#include <iterator>
#include <list>
#include <limits>
#include <set>
#include <utility>
#include <vector>
///////////////////////////////////////////////////////////////////////////////
typedef int                                     T_point;
typedef T_point                                 T_diff;
typedef std::vector     < T_point   >           T_points;
typedef std::pair       < T_point,  T_diff  >   T_point_data;
typedef std::list       < T_point_data      >   T_points_data_list;
typedef T_points_data_list::iterator            T_point_data_it;
///////////////////////////////////////////////////////////////////////////////
const   T_diff  DIFF_EMPTY  =   std::numeric_limits< T_diff >::max();
///////////////////////////////////////////////////////////////////////////////
namespace   std
{
    bool    operator<
        (
            T_point_data_it     const   &   L,
            T_point_data_it     const   &   R
        )
    {
        return      std::make_pair( L->second,  L->first    )
                <   std::make_pair( R->second,  R->first    );
    }
}
///////////////////////////////////////////////////////////////////////////////
typedef std::set    < T_point_data_it   >   T_iterators;
///////////////////////////////////////////////////////////////////////////////
template < typename     TT_it >
TT_it   get_prev_it( TT_it  const   &   it )
{
    return  --TT_it( it );
}
///////////////////////////////////////////////////////////////////////////////
template < typename     TT_it >
TT_it   get_next_it( TT_it  const   &   it )
{
    return  ++TT_it( it );
}
///////////////////////////////////////////////////////////////////////////////
void    recalc_and_save_point_data_except_first_and_last_it
    (
        T_point_data_it     const   &   it,
        T_iterators                 &   iterators
    )
{
    if  (
                it->second
            ==  DIFF_EMPTY
        )
    {
        return;
    }
 
    auto    it_prev     =   get_prev_it( it );
    auto    it_next     =   get_next_it( it );
 
    auto    diff        =       it_next->first
                            -   it_prev->first;
 
    it->second          =   diff;
 
    iterators.insert( it );
}
///////////////////////////////////////////////////////////////////////////////
T_diff     max_critical_distance
    (
        size_t                  flags_total,
        T_points    const   &   points
    )
{
    T_points    unique_points;
 
    std::unique_copy
        (
            points.begin        (),
            points.end          (),
            std::back_inserter  ( unique_points )
        );
 
    if  (
                flags_total
            >   unique_points.size()
        )
    {
        return  0;
    }
 
    if  (
            flags_total     ==  2
        )
    {
        return      points.back     ()
                -   points.front    ();
    }
 
    T_points_data_list  points_data_list;
    T_iterators         iterators;
 
    for( size_t  i{}; i < unique_points.size(); ++i )
    {
        T_point_data    point_data
                            {
                                unique_points[i],
                                DIFF_EMPTY
                            };
 
        if  (
                    i   >   0
                &&  i   <   unique_points.size()    -   1
            )
        {
            auto    diff        =       unique_points[i + 1]
                                    -   unique_points[i - 1];
 
            point_data.second   =   diff;
        }//if
 
        points_data_list.emplace_back( point_data );
 
        iterators.insert
            (
                --points_data_list.rbegin().base()
            );
    }//for
 
    while   (
                    points_data_list.size()
                >   flags_total
            )
    {
        auto    it          =   *iterators.begin();
        auto    it_prev     =   get_prev_it( it );
        auto    it_next     =   get_next_it( it );
 
        iterators           .erase( it_prev );
        iterators           .erase( it      );
        iterators           .erase( it_next );
 
        points_data_list    .erase( it      );
 
        recalc_and_save_point_data_except_first_and_last_it
            (
                it_prev,
                iterators
            );
 
        recalc_and_save_point_data_except_first_and_last_it
            (
                it_next,
                iterators
            );
    }//while
 
    auto    it          =   *iterators.begin();
    auto    it_prev     =   get_prev_it( it );
    auto    it_next     =   get_next_it( it );
 
    return  std::min    (
                            it_next ->first     -   it      ->first,
                            it      ->first     -   it_prev ->first
                        );
}
///////////////////////////////////////////////////////////////////////////////
int     main()
{
    int     points_total    {};
    int     flags_total     {};
 
    std::cin    >>  points_total
                >>  flags_total;
 
    T_points    points( points_total );
 
    for( auto   &   point   :   points )
    {
        std::cin    >>  point;
    }
 
    std::cout   <<  max_critical_distance
                        (
                            flags_total,
                            points
                        )
 
                <<  std::endl;
}
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru