Разделите список!

10

В этой задаче вам нужно разделить список, где разделы имеют максимальный размер, минимальный размер и предпочтительный размер. Я буду использовать обозначение, (min,pref,max) чтобы указать размеры в этой задаче.

Для тех, кто не знаком с разделением, следующий список был разделен на части 3:
[0..9] -> [[0,1,2],[3,4,5],[6,7,8]]

Если список не нацело, вам нужны разделы , чтобы быть как можно ближе к предпочтительному размеру , насколько это возможно: [0..10], (2,4,5) -> [[0,1,2,3],[4,5,6],[7,8,9]]. Такое разбиение предпочтительнее [[0,1,2,3],[4,5,6,7],[8,9]], даже если последний имеет большую предпочтительную длину. Формально нам нужно минимизировать сумму (partitionLength-preferredSize)^2для каждого раздела.

Порядок длин разделов не имеет значения: Для [0..5], (2,3,3)либо [[0,1,2],[3,4]]или [[0,1],[2,3,4]]работы. Если нет раздела не возможно, возвращает пустой массив: [0..7], (4,4,5) -> [].

Вы можете предположить, что 1<=min<=pref<=maxи что переданный вам массив является непустым массивом целых чисел. Массив всегда будет первым аргументом. Вы можете принимать min, max и pref в любом порядке, в виде кортежа или отдельных аргументов.

Ваша программа должна работать менее чем за пару секунд. По сути, перебирать каждый возможный размер раздела в пределах границ не разрешается.

Тестовые случаи:

[1], (1,3,4)         -> [[1]]
[100], (1,2,3)       -> [[100]]
[1,2], (1,1,2)       -> [[1],[2]]
[1,2], (1,2,2)       -> [[1,2]]
[1,2], (1,3,3)       -> [[1,2]]
[1,2,3], (1,2,3)     -> [[1,2],[3]] or [[1,2,3]]
[1,2,3,4], (1,3,4)   -> [[1,2,3,4]]
[1,2,3,4,5], (3,3,4) -> []
[1,2,3,4,5], (2,2,2) -> []
[1,2,3,4,5], (3,3,5) -> [[1,2,3,4,5]]
[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], (2,6,6) -> [[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]]

Это , поэтому старайтесь использовать как можно меньше байтов на своем любимом языке!

Натан Меррилл
источник
Используемая вами запись [a..b]включает aи исключает b, верно?
Алекс А.
A включительно, B эксклюзивно.
Натан Меррилл
Обратите внимание, что ваша интерпретация a - это не то же самое, что раздел из теории множеств ...
всегда
Но это эффективно эквивалентно целочисленного секционирования.
Натан Меррилл
Что делать, если нет решения?
feersum

Ответы:

2

Хаскелл, 152

_%0=[]
s%k|(a,b)<-splitAt(div(z s)k)s=a:b%(k-1)
z=length
f s n p x=snd$minimum$(z s*p^2,[]):[(sum[(z x-p)^2|x<-s%k],s%k)|k<-[-div(-z s)x..div(z s)n]]

В любом разделе, если есть два списка, длина которых различается на два или более, всегда будет полезно уменьшить больший список и увеличить меньший список. поэтому нам нужно рассмотреть только разделы только с двумя размерами списка, что упрощает вычисления.

Затем программа запускает все возможные списки в разделе. учитывая количество списков в разделе, оценка определяется однозначно. программа вычисляет подходящий раздел и его оценку.

затем он находит общий минимум и возвращает его.

Использование: ввод, как f [1,2,3,4,5] 1 3 4( fэто функция, которая решает задачу)

Хотя можно вычислить лучший вариант полностью численно и только затем соответствующим образом разделить список, это заняло слишком много байтов. тем не менее, моя последняя версия этого подхода:

_%0=[]
s%k|(a,b)<-splitAt(div(length s)k)s=a:b%(k-1)
f s n p x|l<-length s=(s%)$snd$minimum$(l*p^2,0):[(k*j^2+mod l k*(1-2*j),k)|k<-[1..div l n],k*x>=l,j<-[p-div l k]]
гордый хаскеллер
источник
1

CJam, 70

q~:S;_,[0L]a{_S2=e<),S0=>f{[__S1=-_*\]@@-j.+}[esL]a+:e<}j1={/(\e_}/;]p

Попробуйте онлайн

Код находит оптимальную последовательность размеров разделов в зависимости от размера списка, используя динамическое программирование (с помощью запомненной рекурсии), затем идет вперед и разбивает список на части.

уйти, потому что SE это зло
источник