Алгоритм разбиения массива

alex_deads

Пусть имеется одномерный массив x(i в количестве N элементов, ТРЕБУЕТСЯ составить алгоритм, при помощи которого этот массив можно разделить его на k подряд идущих групп элементов (начиная с первого элемента и оканчивая последним так чтобы максимальный размер (разность между максимальным и минимальным) группы по множеству всех групп был минимальным.
Например. x(i)={1,2,5,6,7,9,10} k=3, тогда искомое разбиение (1,25,79,10). Т.к. максимальный размер: 2-1=1 7-5=2 10-9=1 равен 2. При всевозможных других разбиениях эта величина больше или равна 2.
Где можно посмотреть подобные алгоритмы?

Vadim46

а тупо динамикой это разве не делается?

alex_deads

Т.е. перебором, это оч много получается, порядка N в степени k-1, ну или (N^(k-2* log N Задача состоит в том как оптимизировать это?
Или я неправильно понимаю, что значит динамикой?

Vadim46

Нет, кажется, порядка N^2*k. Решаем аналогичную задачу с параметрами (i, j где i - индекс массива, начиная с которого мы ищем разбиение, второй - на сколько групп разбиваем. i<=N, j<=k, на решение очередной задачи уходит О(i) времени (перебор всех возможностей для первой группы)

alex_deads

Я забыл указать условие того что массив упорядочен. В этом случае например для k=2, понятно что необходимо найти элемент x(j) такой что x(j)<(max+min)/2, а x(j+1)>(max+min)/2, т.к. min=x(1) max=x(N Искомое разбиение (x(1x(jx(j+1x(N ищется за logN двочным делением.

Vadim46

Ну для k>2 я с ходу не вижу как это применить
а (N^2)*k не устраивает ?

alex_deads

т.е. (N в квадрате) * K, я правильно понимаю? Можно еще раз уточнить как это делается?

alex_deads

или N в степени 2k, если так, то это многовато!

Vadim46

решаем такие же задачи, но массив берем начиная с i-го индекса и разбиваем на j групп. В таком порядке: i=N, j=1; i=N-1, j=1; ... i=1, j=1; i=N, j=2; i=N-1, j=2; ....
Результаты запоминаем.
Чтобы решить очередную подзадачу, надо рассмотреть O(i) вариантов для первой группы и воспользоваться уже известным результатом предыдущей подзадачи, чтобы выбрать из них наилучший.

soldatiki

Или я туплю, или решается за О(эн): берем разницу между максимальным и минимальным элементами (один в начале, другой в конце делим на число "пачек" и обзываем это дело скачком. Идем по массиву и отмечаем пачки. Очередной элемент попадает в текущую пачку, если разность между ним и первым элементом пачки меньше скачка, иначе "закрываем" текущую пачку и открываем новую.

Vadim46

контрпример 1 2 3 4 100000 100001 100000002 100000003, k=3

soldatiki

Да, согласен. Тогда так: за один проход вычисляем для каждого элемента разность между ним и следующим. Попутно храним (в куче) k максимальных значений такой разности и индексы. Найденные k элементов - это те, где происходит максимальный скачок, значит, там должна заканчиваться одна и начинаться другая группа.

Vadim46

k максимальных значений храним или k-1 ?
вот еще пример: 1 2 3 4 5 6 7 8 9 10 12, k=2

ulia06

я бы попросил уточнить условия: минимальное число элементов в пачке равно чему -раз, равны ли размеры пачек -два.

ulia06

а в твоем первом контрпримере делаем вложение (если пачки могут быть не равны по количеству входящих в них элементов, естественно). Пока число элементов мин. пачки большеравно двум (думаю, условие на минимум элементов таково) применяем схему страйкера. Единственное -проверять надо будет для всех простых, которые у нас попадают до "общего числа элементов".

Vadim46

я ничего не понял :( что значит вложение, что надо проверять для простых? :confused: можешь подробнее написать?

ulia06

разбиваем массив на n пачек, отрезаем куски (пусть n=2) и "скатываемся" внутрь отрезанного куска, проверяя, можно ли его "разрезать" на ещё более мелкие с точки зрения расстояния между элементами, ныряем ещё глубже. Если разбить дальше некуда -запоминаем результат, выныриваем. Получается рекурсия.
Выныриваем - скатываемся во второй кусок "разбиения", делаем то же самое, "доныриваем" до дна, сравниваем результаты, выныриваем - до самого верха.
Сделали сие кошерное действо для двух пачек (хотя можено сразу оптимизировать,я так думаю) - проверяем для трех, потом для пяти, потом для семи ...
Думаю, тут тоже можно ускориться. надо только подумать, какие из "перепроверок" излишни.

ulia06

кстати, сразу в лоб: число пачек не может превосходить n/2, где n - число всех элементов массива (если в каждой из пачек должно быть не менее двух элементов).
причем это правило будет справедливо для каждого из "вложенных" кусков.
ну, и ещё поясню: это все справедливо для случая когда длина пачек ничем не регламентирована. по крайней мере, мне пока кажется, что справедливо :o

Vadim46

я короче вообще ничего не понял :grin:
у тебя кол-во пачек переменное, что ли? оно же задано
продемонстрируй на 1м примере, что ли..
ну да, я тоже так понял, что на длину нет ограничений

ulia06

упс... сорри, у меня действительно количество пачек переменное :o

kiritsev

есть простое решение за ln (x(n)-x(1 * n которое для обычных чисел будет работать очень быстро.
алгоритм должен быть понятен из оценки =)
Оставить комментарий
Имя или ник:
Комментарий: