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

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

Восстановить пароль Регистрация
 
сроропропро
0 / 0 / 0
Регистрация: 06.11.2015
Сообщений: 7
11.07.2016, 11:19     Разместить флажки на прямой как можно дальше друг от друга #1
На прямой отмечены 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
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
MansMI
1046 / 843 / 205
Регистрация: 08.01.2012
Сообщений: 3,023
11.07.2016, 13:39     Разместить флажки на прямой как можно дальше друг от друга #2
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
void flags(int*an,int n,int*am,int m,int k,int p,int&l)
{
    int imax=n-m+k;
    for(int i=p; i<=imax; i++)
    {
        am[k]=i;
        if(k+1<m) flags(an,n,am,m,k+1,i+1,l);
        else
        {
            int imin=0;
            for(int j=1; j<m-1; j++)
            if(an[am[imin+1]]-an[am[imin]]>an[am[j+1]]-an[am[j]])imin=j;
            int lmax=an[am[imin+1]]-an[am[imin]];
            if(lmax>l) l=lmax;
        }
    }
}
 
void main(int argc,char* argv[])
{
    int  n,m;
    setlocale(LC_ALL,"Rus");
    cout<<"N и M через пробел:";
    cin>>n>>m;
    int *an=new int[n];
    int *am=new int[m];
    for(int i=0; i<n; i++)
    {
        cout<<"N["<<i<<"]:";
        cin>>an[i];
    }
    int l=0;
    flags(an,n,am,m,0,0,l);
    cout<<l<<endl;
    delete[] an;
    delete[] am;
    system("pause");
}
сроропропро
0 / 0 / 0
Регистрация: 06.11.2015
Сообщений: 7
11.07.2016, 15:58  [ТС]     Разместить флажки на прямой как можно дальше друг от друга #3
Time Limit, нужно что-то быстрее
MansMI
1046 / 843 / 205
Регистрация: 08.01.2012
Сообщений: 3,023
11.07.2016, 16:41     Разместить флажки на прямой как можно дальше друг от друга #4
что за лимит?
сроропропро
0 / 0 / 0
Регистрация: 06.11.2015
Сообщений: 7
11.07.2016, 18:05  [ТС]     Разместить флажки на прямой как можно дальше друг от друга #5
Нужно чтобы алгоритм работал не более 2-х секунд
MansMI
1046 / 843 / 205
Регистрация: 08.01.2012
Сообщений: 3,023
11.07.2016, 18:13     Разместить флажки на прямой как можно дальше друг от друга #6
ну и кликай побыстреее
Цитата Сообщение от сроропропро Посмотреть сообщение
Входные данные
где вход то?
сроропропро
0 / 0 / 0
Регистрация: 06.11.2015
Сообщений: 7
11.07.2016, 19:39  [ТС]     Разместить флажки на прямой как можно дальше друг от друга #7
Не пойму, что сложного в условии? Эту задачку проверяет машина, если она работает более 2-х сек, то time limit
MansMI
1046 / 843 / 205
Регистрация: 08.01.2012
Сообщений: 3,023
11.07.2016, 19:46     Разместить флажки на прямой как можно дальше друг от друга #8
да ничего сложного, наколоти
Цитата Сообщение от сроропропро Посмотреть сообщение
5 3
0 3 4 4 9
за менее 2 сек, получилось?
Цитата Сообщение от сроропропро Посмотреть сообщение
N ≤ 10^5
тогда вот еще вариант
сроропропро
0 / 0 / 0
Регистрация: 06.11.2015
Сообщений: 7
11.07.2016, 21:37  [ТС]     Разместить флажки на прямой как можно дальше друг от друга #9
Я понимаю, но я сам не конкретные цифры в тестах, смысл такой, что это решение не проходит, нужно что-то быстрее
MansMI
1046 / 843 / 205
Регистрация: 08.01.2012
Сообщений: 3,023
11.07.2016, 21:48     Разместить флажки на прямой как можно дальше друг от друга #10
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
int n, m, l=0;
int an[100000],am[100000];
void flags(int k,int p)
{
    int imax=n-m+k;
    for(int i=p; i<=imax; i++)
    {
        if(k && an[i]-an[am[k-1]]<=l) continue;
        am[k]=i;
        if(k+1<m) flags(k+1,i+1);
        else
        {
            l=an[am[1]]-an[*am];
            for(int j=1; j<m-1; j++)
            {
                int ll=an[am[j+1]]-an[am[j]];
                if(l>ll) l=ll;
            }
        }
    }
}
 
void main(int argc,char* argv[])
{
    ifstream fin("input.txt");
    fin>>n>>m;
    for(int i=0; i<n; i++) fin>>an[i];
    fin.close();
    flags(0,0);
    cout<<l<<endl;
    system("pause");
}
надоело мне вводить, "input.txt" сами слепите
сроропропро
0 / 0 / 0
Регистрация: 06.11.2015
Сообщений: 7
11.07.2016, 23:30  [ТС]     Разместить флажки на прямой как можно дальше друг от друга #11
Спасибо большое что помогаете, но к сожалению опять time limit на том же самом тесте. А можете рассказать ход вашего решения на словах?
zer0mail
12.07.2016, 07:09
  #12

Не по теме:

Цитата Сообщение от сроропропро Посмотреть сообщение
Я понимаю, но я сам не конкретные цифры в тестах, смысл такой, что это решение не проходит, нужно что-то быстрее
Олимпиадные задачи для того, чтобы найти тех, кто сам может решать и находить это "быстрее". Умельцы копировать чужие ответы не нужны.

MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.07.2016, 07:31     Разместить флажки на прямой как можно дальше друг от друга
Еще ссылки по теме:

Структуры с указателями друг на друга C++
C++ Как позволить функциями видеть друг друга?
C++ Как сделать чтобы авто не наезжали друг на друга и не столкнулись

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Mr.X
Эксперт С++
 Аватар для Mr.X
2799 / 1575 / 246
Регистрация: 03.05.2010
Сообщений: 3,656
13.07.2016, 07:31     Разместить флажки на прямой как можно дальше друг от друга #13
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;
}
Yandex
Объявления
13.07.2016, 07:31     Разместить флажки на прямой как можно дальше друг от друга
Ответ Создать тему
Опции темы

Текущее время: 13:09. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru