«phpClub» — архив тем ("тредов"), посвящённых изучению PHP и веб-технологий.
Аноним 2018/04/24 15:25:27  №1178922 1
Сап анонимусы, работодатель на интервью подкинул задачку на алгоритмы, пытался написать на пыхе, но ничего дельного не вышло:
Расстояние между А и В 18 км, первая заправка находится от А на расстоянии 9 км, расстояние от первой до след. заправки 4 км, от второй до B 5 км. Нужно оптимально разместить три новые заправки (помимо этих трех, эти три перемещать нельзя) чтобы минимизировать максимальное расстояние между двумя заправками подряд (на всем маршруте).
Т.е. имеем массив [9,4,5] и количество заправок k = 3, нужно конкретно для этой задачи получить массив [3,3,3,4,2.5,2.5], но как это сделать алгоритмически и для любых данных, ума не приложу..
пс может вопрос тупой, сори, но если кто сталкивался или сообразит хелп плз! Всем мир!
Ответы: >>1178943 >>1178985 >>1179124
Аноним 2018/04/24 16:44:33  №1178985 2
>>1178922
Смотри как тебе такое универсальное решение
На вход берешь массив сегментов и количество разделений которые нужно добавить.

Делишь 18 (общая длинна) / 5 (общее количество разделителей) = 3.6 - best т.е. в идеальном мире если бы заправки можно было двигать... заодно если у тебя всего один сегмент то ответ уже готов.

Вычисляешь
9 4 5 - наш массив ; 3 - остаток бюджета делителей
5.4 0.4 1.4 - отклонения сегментов от идеального; 2.4 - среднее отклонение

Берешь первый отрезок с самым большим отклонением и делаешь вот что: делишь его по очереди на разное количество сегментов в бюджете и считаешь среднее отклонение. Лучший разрез даст наименьшее отклонение.

4.5 4.5 4 5 ; 2
0.9 0.9 0.4 1.4 ; 0.9

3 3 3 4 5 ; 1
0.6 0.6 0.6 0.4 1.4 ; 0.72

2.25 2.25 2.25 2.25 4 5 ; 0
1.35 1.35 1.35 1.35 0.4 1.4 ; 1.2

Выбираем разрез на 3 части, в бюджете остается еще разрез. Повторим алгоритм, теперь резать будем 5, но так как вариант порезать сегмент всего один (у нас один разрез) то сразу получаем конечный результат:

3, 3, 3, 4, 2.5, 2.5 ; 0
0.6, 0.6, 0.6, 0.4, 1.1, 1.1 ; 0.88

Предположим другие входные данные:
50 22 2 9; 5; ( 10.375 )
Поехали:
25 25 22 2 9; 4; 10.125
16.66 16.66 16.66 22 2 9; 3; 6.7
12.5 12.5 12.5 12.5 22 2 9; 2; 4.26
10 10 10 10 10 22 2 9; 1; 2.9
8.33 8.33 8.33 8.33 8.33 8.33 22 2 9; 0; 3.73
Выбираем вариант с разделением на пять частей (тратим 4 делителя):
10 10 10 10 10 22 2 9; 1; 2.9
Ну думаю уже догадался что мы поделим и что получится.

На вскидку кажется нет узких мест.

Теперь давай попробуем прикинуть алгоритмическую сложность:
Первое: перед каждым разрезом мы проходимся по массиву для поиска самого большого куска, это N. Операцию выбора большого куска придется также повторить до тех пор пока k не кончится - N k, но так как k уменьшается то N log( k )
Второе: чтобы найти лучший разрез мы делим наш кусок на k..1 и каждый раздел расчитываем, это еще раз k, так что k ^ 2, но так как k уменьшается то log ( k ^ 2 )

Вторую операцию мы повторяем столько раз сколько дает первая, т.е.: N log( k ) log ( k ^ 2 )
Алгоритмическая сложность если я правильно понимаю O( N log( k ) log ( k ^ 2 ) )
Надеюсь если будет кто шарящий читать поправит.

Пойду устраиваться вместо тебя