Cięcie równych drążków z różnych drążków

Masz drążków o dowolnej długości, niekoniecznie integralnych.$n$

Cięcie niektórych patyków (jedno cięcie tnie jeden patyk, ale możemy ciąć tak często, jak chcemy), chcesz uzyskać takich, aby:$k<n$

• Wszystkie te kije mają taką samą długość;$k$
• Wszystkie kije są co najmniej tak długie, jak wszystkie inne kije.$k$

Pamiętaj, że po wykonaniu cięć uzyskujemy drążki$n + C$$C$

Jakiego algorytmu byś użył, aby liczba niezbędnych cięć była minimalna? A jaki jest ten numer?

Jako przykład weźmy i dowolne . Można zastosować następujący algorytm:n ≥ $k=2$$n\geq 2$

• Uporządkuj drążki, malejąco według długości, aby .$L_1\geq L_2 \geq \ldots \geq L_n$
• Jeśli pociąć drążek nr 1 na dwie równe części. Istnieją teraz dwa drążki o długości , które są co najmniej tak długie, jak pozostałe drążki .L 1 / 2 2 ... $L_1\geq 2 L_2$$L_1 / 2$$2 \ldots n$
• W przeciwnym razie ( ) pociąć drążek nr 1 na dwa nierówne kawałki o rozmiarach i . Istnieją teraz dwa drążki o długości , która jest dłuższa niż a pozostałe drążki .L 2 L 1 - L 2 L 2 L 1 - L 2 3 … $L_1 < 2 L_2$$L_2$$L_1-L_2$$L_2$$L_1-L_2$$3 \ldots n$

W obu przypadkach wystarczy jedno cięcie.

Próbowałem uogólnić to na większe , ale wydaje się, że jest wiele przypadków do rozważenia. Czy potrafisz znaleźć eleganckie rozwiązanie?$k$

Pierwszą podstawową obserwacją do rozwiązania tego problemu jest to, że wykonalność długości cięcia ,$l$

,$\qquad\displaystyle \operatorname{Feasible}(l) = \biggl[\, \sum_{i=1}^n \Bigl\lfloor\frac{L_i}{l} \Bigr\rfloor \geq k \,\biggr]$

jest stały kawałek, lewy ciągły i nie rośnie w . Ponieważ liczba niezbędnych cięć zachowuje się podobnie, znalezienie optymalnej długości jest po prostu odpowiednie$l$

$\qquad\displaystyle l^{\star} = \max \{ l \mid \operatorname{Feasible}(l) \}$

Ponadto, jak sugerują inne odpowiedzi, wszystkie nieciągłości skoku mają postać . To pozostawia nam dyskretny, jednowymiarowy problem wyszukiwania, który może być przeszukiwany binarnie (po posortowaniu skończonego zestawu kandydatów).$L_i/j$

Zauważ ponadto, że musimy wziąć pod uwagę tylko które są krótsze niż największy, ponieważ jest to zawsze możliwe.$L_i$$k$

Następnie różne granice prowadzą do algorytmów o różnej wydajności.$j$

• $1 \leq j \leq k$ powoduje, że przestrzeń wyszukiwania ma kwadratowy rozmiar (w ),$k$
• L $1 \leq j \leq \lceil k/i \rceil$ w (zakładając, że są sortowane według malejącego rozmiaru), i$L_i$
• nieco więcej zaangażowanych granic w liniową.

Korzystając z tego, możemy rozwiązać proponowany problem w czasie i spacja .Θ ( n + k $\Theta(n + k \log k)$$\Theta(n + k)$

Kolejnym spostrzeżeniem jest to, że suma w rośnie w o dla każdego kandydata „zdał”, licząc duplikaty. Korzystając z tego, możemy użyć wyboru rangi zamiast wyszukiwania binarnego i uzyskać algorytm działający w czasie i przestrzeni , który jest optymalny. l 1 L i / j Θ ( n $\mathrm{Feasible}$$l$$1$$L_i/j$$\Theta(n)$

Znajdź szczegóły w naszym artykule Efektywne algorytmy dla podziału kija bez zazdrości o najmniejszych cięciach (Reitzig i Wild, 2015).

Zgodnie z sugestią @randomA, przejdziemy do dwóch etapów: Najpierw znajdziemy zestaw lasek, które zostaną wycięte, a następnie zminimalizujemy liczbę cięć.

Podobnie jak w przypadku szczególnym w pytaniu, sortujemy / nazywamy patyki tak, aby . Zajmuje to czas . O ( n log n $L_1 \ge L_2 \ge \dots \ge L_n$$O(n\log n)$

@ User1990169 jak podkreślił, nie musimy wyciąć kawałek .$i\ge k$

W pierwszej fazie wykorzystujemy wyszukiwanie binarne w celu znalezienia liczby , , aby kije można było pociąć na co najmniej kawałków o rozmiarze (plus kilka mniejszych) , ale drążków nie można pokroić na kawałków o rozmiarze . Zajmie to czas .1 ≤ s ≤ k 1 , … , s k L s 1 , … , s - 1 k L s - 1 O ( k log k $s$$1\le s \le k$$1, \dotsc, s$$k$$L_s$$1, \dotsc, s-1$$k$$L_{s-1}$$O(k\log k)$

Jeśli , ta wartość jest optymalnym rozmiarem i możemy pominąć fazę drugą.$L_{s-1} = L_s$

W przeciwnym razie wiemy, że optymalna wielkość spełnia a jeśli następnie wynikach cięcia co najmniej jeden z patyczków na równe wielkości kawałki. Faza druga określi :$o$$L_{s-1} > o \ge L_s$$o > L_s$$o$$o$

Dla każdego kija , określ zestaw rozmiarów kandydatów w następujący sposób: Jeśli cięcie na kawałki o rozmiarze zamienia kij na kawałki (w tym krótszy, jeśli taki istnieje), kandydaci na to stick to wszystkie wartości , gdzie i . (Zobacz odpowiedź @ user1990169, aby dowiedzieć się, dlaczego są to jedyne rozmiary kandydatów).$i$$1\le i \le s$$L_s$$r_i$$\frac{L_i}j$$j\le r_i$$\frac{L_i}j<L_{s-1}$

Zachowaj dla każdego rozmiaru kandydata, jak często to miało miejsce. Korzystając ze zrównoważonego drzewa wyszukiwania, można to zrobić w , ponieważ całkowita liczba kandydatów jest ograniczona przez .$O(k\log k)$$\sum_i r_i \le 2k$

Teraz najczęściej wybierany rozmiar, który prowadzi do prawidłowego cięcia, to taki, który zapewnia nam optymalne rozwiązanie. Ponadto, jeśli jakikolwiek rozmiar kandydujący prowadzi do prawidłowego cięcia, każdy mniejszy rozmiar doprowadzi również do prawidłowego cięcia.

Możemy więc ponownie zastosować wyszukiwanie binarne, aby znaleźć największą długość kandydata, która prowadzi do prawidłowego cięcia w . Następnie iterujemy zestaw długości kandydatów do tego progu i znajdujemy tę o największej liczbie spośród nich w .$O(k\log k)$$O(k)$

W sumie otrzymujemy środowisko wykonawcze w lub , jeśli zignorujemy (lub nie będziemy musieli) sortować początkowe.$O(n\log n)$$O(k\log k)$

Po uporządkowaniu drążków w kolejności malejącej według ich długości, drążek zostanie przecięty tylko wtedy, gdy wszystkie drążki zostaną przecięte.$L_i$$L_1, L_2, ... L_{i-1}$

Odkąd , nie będziemy robić nacięć na dalej, ponieważ zawsze możemy mieć drążków o długości .L k k L $k < n$$L_{k}$$k$$L_{k}$

Więc teraz zamiast mamy do czynienia tylko z kijami (ewentualnie dodając ty kij jako całość), a maksymalna liczba cięć, które będą wymagane w najgorszym przypadku .k - 1 k = k - $n$$k-1$$k$$= k-1$

Ponadto, jeśli optymalna liczba cięć wynosi , to wśród tych drążków musi znajdować się co najmniej jeden zestaw drążków, które należy pobrać w całości z 1 oryginalnego drążkak - $< k-1$$k-1$ (w częściach lub w jednym kawałku) , tj. żadna część tego oryginalnego patyka nie może pozostać „niewykorzystana”. Wynika to z tego, że zgodnie z zasadą gołębnika należy wykonać co najmniej 1 cięcie, które będzie musiało wytworzyć więcej niż 1 ważny sztyft.

Następnie możesz przeprowadzić dwa zagnieżdżone dla pętli (oba do ). Pętla zewnętrzna oznacza numer patyka którego wszystkie części muszą zostać pobrane, a pętla wewnętrzna oznacza liczbę części wykonanych z tego patyka. Dla każdego rozmiaru sprawdź, czy możesz uzyskać wykonalne kijki, przecinając kolejno i jeśli to możliwe, zaktualizuj wymagane do tej pory minimalne cięcia, jeśli aktualna wymagana liczba jest mniejsza.i j L $k$$i$$j$
L$\frac{L_i}{j}$$L_1$

Całkowita złożoność powyższego algorytmu wynosi$O(nlog(n) + k^3)$

Ideą wysokiego poziomu byłoby wyszukiwanie binarne.

Rozmiar każdego z wymaganych drążków k będzie wynosił co najmniej najmniejszy drążek, a co najwyżej największy. Z tego powodu kontynuujemy wyszukiwanie binarne na podstawie rozmiaru środkowego drążka, zobaczmy, jaką liczbę możemy uzyskać, jeśli to jest większe niż podane to wiemy, że musimy wybrać nowy referencyjny rozmiar kandydata. Więc przechodzimy do większego lub mniejszego za pomocą nowego drążka odniesienia. Zatrzymujemy się, gdy jest mniejsze niżk ′ k k ′$k'$$k'$$k$$k'$$k$

Po znalezieniu odpowiedniego drążka referencyjnego pojawia się narożny futerał, w którym należałoby jeszcze bardziej ulepszyć rozmiar. Możemy posortować wszystkie nacięte pałeczki według liczby nacięć na nich i wielkości patyka. Wybierz ten, który ma najmniejszą liczbę cięć i najmniejszy rozmiar. Zmniejsz liczbę cięć na tym drążku o 1 i zrób wszystkie drążki tego samego rozmiaru. To będzie nowy rozmiar odniesienia, sprawdź, czy ten nowy rozmiar może prowadzić do akceptowalnego . Przyznaję, że nie wiem, jak ograniczyć czas pracy w tym przypadku.$k'$

Mam nadzieję, że widzę coś pożytecznego z innych odpowiedzi.