Minimalizacja kroki do dystrybucji za cukierki w kręgu

Question

Istnieje n dzieci w kole. Każda z nich ma cukierki (może być ujemna, dodatnia lub zerowa). Mogą dawać po jednym cukierku swoim sąsiadom. Końcowym rezultatem jest to, że wszyscy powinni mieć zero cukierków w minimalnych krokach.

Załóżmy, że mamy 4 (-4, -2, 4, 2) dzieciom cukierki to sekwencja będzie

1. (-3, -2, 4, 1)
2. (-2, -2, 4, 0)
3. (-2, -1, 3, 0)
4. (-2, 0, 2, 0)
5. (-2, 1, 1, 0)
6. (-2, 2, 0, 0)
7. (-1, 1, 0, 0)
8. (0, 0, 0, 0)

Jest to jedna z możliwych odpowiedzi, muszę znaleźć minimalną liczbę kroków.

• Loop 1: znaleźć, jeśli sąsiad ma pozytywny cukierki, a następnie podać go do sąsiada z negatywnymi cukierki cukierki, aż liczba jest równa zero i dodać liczbę cukierków udzielonych sumy.

• Pętla 2: znajdź, czy sąsiad sąsiadów ma pozytywne cukierki, a następnie daj je sąsiadowi z negatywnymi cukierkami, aż liczba cukierków będzie równa zeru i dodaj 2 (liczba słodyczy podana do sumy).

• i tak dalej.

Złożoność mojego rozwiązania powoduje TLE. Co mogę zrobić, aby zmniejszyć złożoność?

Answer 1

Nie sądzę, trzeba rundzie pętli w szczegółach. Napisz liczbę cukierków w każdym miejscu jako X1, X2, X3, X4. Załóżmy, że X1 otrzymuje k cukierków z lewej (czyli dla X4). Po tym ma cukierki X1 + K, więc musi przejść to na prawo. Wtedy X2 będzie miało cukierki X1 + X2 + K, więc musi przejść to po jego prawej stronie. X3 będzie miał cukierki X1 + X2 + X3 + K, więc musi przejść to do X4. Wiemy, że X4 przekazało k cukierki, i to sprawdza (zakładając, że X1 + X2 + X3 + X4 = 0, a jeśli nie, to nie ma rozwiązania).

To trwa | k | + | X1 + k | + | X1 + X2 + k | + | X1 + X2 + X3 + k | kroki, więc jeśli zgadujemy, k wiemy, ile kroków należy wykonać. Jaka jest najlepsza wartość k? Jeśli zwiększymy k, zwiększymy sumę, jeśli jest więcej + ve terminów X1 + X2 + ... k, i zmniejszamy, jeśli jest więcej niż -ve terminów. Zatem najlepszą wartością k jest ta, w której dokładnie połowa terminów | k |, | X1 + k | .. ma + ve i dokładnie połowę -ve, ponieważ jeśli tak nie jest, możemy zwiększyć lub zmniejszyć wartość k, aby rzeczy lepsze - wartość k do wyboru to - mediana 0, X1, X1 + X2, X1 + X2 + X3.

I stwierdziły to dla n = 4 przy swoim przykładzie, ale mam nadzieję, że można wypracować odpowiedź dla ogólnego n od tego.

Answer 2

Jeden meta-podejście, które stosuje się tutaj jest podjęcie algorytm, który sonduje i sprawiają, że oparte na zdarzeniach. Co mam na myśli?

Utrzymuj okrągłą listę zawierającą darczyńców (dzieci z> 0 cukierkami) i chętnych (dzieci z < 0 cukierków).Utrzymuj także kolejkę priorytetową, która zawiera wpis dla każdej sąsiedniej (na liście, a nie w kręgu) pary biorców, której kluczem jest odległość między dawcą a biorcą.

Teraz, zamiast zwiększać odległość pojedynczo, użyj kolejki priorytetowej, aby znaleźć kolejną interesującą rzecz, która się dzieje. Za każdym razem, gdy rozdzielana jest para biorców, jedno lub oboje dzieci opuszczają listę, co powoduje konieczność księgowania O (1) i wstawiania kolejki.

Answer 3

Biorąc mcdowella „s pomysł i wprowadzenie go do moich słów (bo zajęło mi trochę czasu, aby to zrozumieć, zobaczyć here jakiegoś handwringing na ten temat) sprawia, że ​​wygląda następująco. Główne spostrzeżenia są następujące:

• Tak jak można mieć negatywny słodycze, można przekazać negatywną słodycze oraz
• Przechodząc negatywny cukierków w jednym kierunku jest zasadniczo przechodzącej (pozytywny) słodycze w przeciwnym kierunku
• Cokolwiek ilość cukierków, które dziecko ma, wszyscy kończą na zero.

To narzędzie jest następujące: wybierz dowolne dziecko na początek (Dziecko A na poniższym diagramie, gdzie mam 5 dzieci zamiast 4) i wybieramy dowolny kierunek (w naszym przypadku przeciwnie do ruchu wskazówek zegara) i zacznij przekazywać. Każde dziecko musi pozbyć się wszystkich swoich cukierków (pozytywnych lub negatywnych), aby uzyskać zero. Więc dziecko A ma cukierek -2, więc przekazujemy to dziecku B. Po tym dziecku B ma -5 cukierków, więc przekazujemy je dziecku C. Teraz dziecko C ma -4 cukierki i przekazuje je D, i tak dalej. To jest drugi diagram, a wszystkie cukierki są w zera w 13 ruchach.

Schemat Senter nie jest optymalna. Zauważamy, że wszystkie cukierki, które zostały przekazane na diagramie centralnym, są ujemne (z wyjątkiem passa E-> A) i że możemy dodać lub odjąć od pierwszego przejścia na: jeśli A-> B pass to +5 zamiast -2, wtedy wszystkie przejścia będą zwiększane o 7, a E-> Przełęcz byłaby 7 zamiast 0, a na końcu A nadal nie miałaby cukierka. Szukamy więc liczby, dzięki której możemy dostosować wszystkie przebiegi tak, aby zminimalizować sumę wartości bezwzględnych wszystkich przebiegów. Na ostatnim diagramie widzimy, że jeśli dodamy +2 do wszystkich przebiegów, suma wartości bezwzględnych wszystkich przebiegów wynosi 7. Na przykład, gdybyśmy dodali +3, suma byłaby większa. Dlatego staramy się dodać stałą do wszystkich przebiegów, która minimalizuje sumę bezwzględnej wartości wszystkich przebiegów.

P.S. Jeśli ktoś myśli, że nie mam pomysłu na mcdowella mcdowella, z chęcią go usunę.