В этой задаче вам нужно разделить список, где разделы имеют максимальный размер, минимальный размер и предпочтительный размер. Я буду использовать обозначение, (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
, верно?Ответы:
Хаскелл, 152
В любом разделе, если есть два списка, длина которых различается на два или более, всегда будет полезно уменьшить больший список и увеличить меньший список. поэтому нам нужно рассмотреть только разделы только с двумя размерами списка, что упрощает вычисления.
Затем программа запускает все возможные списки в разделе. учитывая количество списков в разделе, оценка определяется однозначно. программа вычисляет подходящий раздел и его оценку.
затем он находит общий минимум и возвращает его.
Использование: ввод, как
f [1,2,3,4,5] 1 3 4
(f
это функция, которая решает задачу)Хотя можно вычислить лучший вариант полностью численно и только затем соответствующим образом разделить список, это заняло слишком много байтов. тем не менее, моя последняя версия этого подхода:
источник
CJam, 70
Попробуйте онлайн
Код находит оптимальную последовательность размеров разделов в зависимости от размера списка, используя динамическое программирование (с помощью запомненной рекурсии), затем идет вперед и разбивает список на части.
источник