W tym wyzwaniu musisz podzielić listę, gdzie partycje mają maksymalny rozmiar, minimalny rozmiar i preferowany rozmiar. Będę używał notacji (min,pref,max) do wskazania rozmiarów w tym wyzwaniu.

Dla tych, którzy nie znają partycjonowania, poniższa lista została podzielona na części 3:
[0..9] -> [[0,1,2],[3,4,5],[6,7,8]]

Gdy lista nie jest podzielny, trzeba partycje być tak blisko do preferowanej wielkości, jak to możliwe: [0..10], (2,4,5) -> [[0,1,2,3],[4,5,6],[7,8,9]]. Podział ten jest korzystniejszy niż [[0,1,2,3],[4,5,6,7],[8,9]], chociaż ten drugi ma większą preferowaną długość. Formalnie musimy zminimalizować sumę (partitionLength-preferredSize)^2dla każdej partycji.

Kolejność długości partycji nie ma znaczenia: Dla [0..5], (2,3,3)albo [[0,1,2],[3,4]]albo [[0,1],[2,3,4]]działa. Jeśli partycja jest możliwe powrót pustą tablicę: [0..7], (4,4,5) -> [].

Możesz założyć, że 1<=min<=pref<=maxi przekazana do ciebie tablica jest niepustą tablicą liczb całkowitych. Tablica zawsze będzie pierwszym argumentem. Możesz zaakceptować min, max i pref w dowolnej kolejności i jako krotkę lub jako osobne argumenty.

Twój program musi działać w ciągu kilku sekund. Zasadniczo, iterowanie przez każdy możliwy rozmiar partycji w granicach jest niedozwolone.

Przypadki testowe:

[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]]

To jest golf golfowy , więc celuj w jak najmniejszą liczbę bajtów w swoim ulubionym języku!

Haskell, 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]]

Na każdej partycji, jeśli istnieją dwie listy o długościach różniących się o dwie lub więcej, zawsze korzystne będzie zmniejszenie większej listy i powiększenie mniejszej listy. dlatego musimy wziąć pod uwagę tylko partycje o tylko dwóch rozmiarach list, co upraszcza obliczenia.

następnie program działa na wszystkich możliwych listach na partycji. biorąc pod uwagę liczbę list w partycji, wynik jest jednoznacznie określony. program oblicza pasującą partycję i jej wynik.

następnie znajduje ogólne minimum i zwraca je.

Zastosowanie: input like f [1,2,3,4,5] 1 3 4( fjest funkcją, która rozwiązuje wyzwanie)

Chociaż możliwe jest obliczenie najlepszej opcji całkowicie numerycznie, a dopiero potem odpowiednie podzielenie listy na partycje, zajęło to zbyt wiele bajtów. jednak moja ostatnia wersja tego podejścia to:

_%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]]

CJam, 70

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

Wypróbuj online

Kod wyszukuje optymalną sekwencję rozmiarów partycji w oparciu o rozmiar listy, używając programowania dynamicznego (poprzez zapamiętaną rekurencję), a następnie przechodzi do podziału listy na partycje.