Chocolate Distribution Problem

Q: Jaka jest złożoność czasowa problemu z rozdzielaniem czekolady?

Sortowanie zajmuje O(n log n) , a przesuwanie okna obejmującego m pakietów zajmuje O(n) , więc łączna złożoność wynosi O(n log n) . Dodatkowe miejsce wynosi O(n) na posortowaną kopię albo O(1) poza samym sortowaniem, jeśli sortujesz dane wejściowe w miejscu.

Q: Czy problem dystrybucji czekoladek jest problemem z oknem przesuwnym?

Tak, okno o stałym rozmiarze przesuwające się po posortowanych pakietach. W przeciwieństwie do okna z sumą bieżącą nie ma nic do aktualizowania podczas jego przesuwania: różnica dla każdego okna to wynik odejmowania pierwszego pakietu od ostatniego.

Q: Czy problem z rozdzielaniem czekolady można rozwiązać bez sortowania?

Rozmiary są tutaj co najwyżej równe 10^5 , więc sortowanie przez zliczanie porządkuje je w czasie O(n + 10^5) i obowiązuje to samo rozumowanie. Przy nieograniczonych rozmiarach same porównania nie pozwalają osiągnąć lepszego czasu niż O(n log n) : dla m = 2 odpowiedź wynosi 0 dokładnie wtedy, gdy dwa pakiety są równe, a wykrycie duplikatu wymaga w najgorszym przypadku tylu porównań.

ŁatweSortowanie Przesuwane okno

+10

Masz kilka paczek czekoladek, a packets[i] to liczba czekoladek w paczce i. Każdy z m uczniów dostaje dokładnie jedną paczkę, więc rozdajesz m różnych paczek. Wybierz je tak, aby różnica między największą a najmniejszą z rozdanych paczek była jak najmniejsza.

Napisz funkcję o nazwie minDifference, która zwraca tę najmniejszą możliwą różnicę.

Funkcja

minDifference(packets: integer-array, m: integer) → integer

packetsinteger-array: liczba czekoladek w każdej paczce
minteger: liczba uczniów, z których każdy otrzymuje jedną paczkę
Zwracainteger: najmniejsza możliwa różnica między największą a najmniejszą paczką, które zostały rozdane

Ograniczenia

2 ≤ m ≤ packets.length ≤ 10⁴
1 ≤ packets[i] ≤ 10⁵
Dwie paczki mogą zawierać taką samą liczbę czekoladek.

Przykłady

Wejście: packets = [9, 3, 15, 7, 11, 4]m = 3
Wyjście: 4
Wyjaśnienie: Po posortowaniu paczki mają wartości 3, 4, 7, 9, 11 i 15. Zarówno 3, 4, 7, jak i 7, 9, 11 dają różnicę 4 i żadne trzy paczki nie są bliżej siebie.

Wejście: packets = [8, 1, 5]m = 3
Wyjście: 7
Wyjaśnienie: Są trzej uczniowie i trzy paczki, więc każda paczka zostaje rozdana, a różnica wynosi 8 - 1 = 7.

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Sprawdzanie każdej grupy m pakietów trwa zdecydowanie za długo. Najlepszy wybór to zawsze m pakietów leżących obok siebie po posortowaniu pakietów. Wystarczy więc posortować je raz, a odpowiedzią będzie najmniejsza różnica w dowolnym oknie m sąsiadujących pakietów, którą można znaleźć w jednym przebiegu.

Napraw najmniejszą paczkę

Poprawne, ale nie kończy się na największych testach

Intuicja

Ustal najmniejszą paczkę, którą rozdajesz: low. Aby największa paczka była jak najmniejsza, wybierz m-1 najmniejszych paczek, które mają co najmniej low. Różnica to wtedy m-ta najmniejsza paczka spośród tych o rozmiarze co najmniej low minus low. Wypróbuj każdą paczkę jako low, pomiń te, dla których jest mniej niż m paczek o rozmiarze równym temu lub większym, i zachowaj najmniejszą różnicę.

Każdy z n wyborów filtruje i sortuje do n paczek: O(n² log n). Przy n = 10^4 różnych rozmiarach same sortowania wymagają około 6 × 10^8 porównań.

Algorytm

Ustaw best na wartość, której żadna odpowiedź nie może przekroczyć.
Dla każdego pakietu low zbierz wszystkie pakiety zawierające co najmniej low czekoladek i posortuj je.
Jeśli jest ich co najmniej m, różnica między m-tym najmniejszym a low jest kandydatem.
Zachowaj najmniejszego kandydata w best i zwróć go.

def minDifference(packets, m):
    best = max(packets) - min(packets)  # no gap can be wider than this
    for low in packets:
        # The packets that could go out alongside low, smallest first (low is one of them).
        bigger = sorted(x for x in packets if x >= low)
        if len(bigger) >= m:
            best = min(best, bigger[m - 1] - low)
    return best

Posortuj i przesuń okno zawierające m pakietów

Intuicja

W uporządkowanym ciągu okno sizes[i..i+m-1] ma najmniejszy pakiet na początku, a największy na końcu, więc różnica wynosi sizes[i+m-1] - sizes[i].

Najlepszy wybór zawsze może być oknem. Jeśli wybór pomija pakiet leżący między najmniejszym a największym, zamień największy pakiet na ten pominięty. Najmniejszy pozostaje bez zmian, a największy może być tylko mniejszy, więc różnica nigdy nie wzrośnie. Powtarzaj, aż nie pozostanie żadna luka.

W pierwszym przykładzie okna złożone z trzech elementów dają 4, 5, 4 i 6, więc odpowiedź to 4. Sortowanie ma złożoność O(n log n), a przesuwanie okna O(n).

Algorytm

Posortuj pakiety rosnąco w sizes.
Ustaw best na sizes[m-1] - sizes[0], czyli pierwsze okno.
Dla każdego początku i od 1 do n-m porównaj sizes[i+m-1] - sizes[i] z best i zachowaj mniejszą wartość.
Zwróć best.

def minDifference(packets, m):
    sizes = sorted(packets)
    best = sizes[m - 1] - sizes[0]
    # The window sizes[i..i+m-1] holds m packets; its first is the smallest, its last the largest.
    for i in range(1, len(sizes) - m + 1):
        best = min(best, sizes[i + m - 1] - sizes[i])
    return best

Pułapki i przypadki brzegowe

Kończenie okna na i+m zamiast na i+m-1, co obejmuje m+1 pakietów.
Zatrzymywanie się o jedno okno za wcześnie. Początkowe indeksy biegną od 0 do n-m włącznie. Dla [1, 10, 20, 21] przy m = 2 pętla z warunkiem i < n-m pomija jedyną różnicę równą 1.
Pominięcie sortowania. W [9, 3, 15, 7, 11, 4] pierwsze trzy pakiety różnią się o 12, podczas gdy odpowiedź wynosi 4.
Mierzenie tylko pierwszego okna. m najmniejszych pakietów to jeden z możliwych wyborów, ale najlepsza grupa może zaczynać się w dowolnym miejscu.
Sortowanie liczb jako tekstu. W JavaScript sort() bez komparatora umieszcza 100000 przed 9.

Najczęstsze pytania3

Jaka jest złożoność czasowa problemu z rozdzielaniem czekolady?

Sortowanie zajmuje O(n log n), a przesuwanie okna obejmującego m pakietów zajmuje O(n), więc łączna złożoność wynosi O(n log n). Dodatkowe miejsce wynosi O(n) na posortowaną kopię albo O(1) poza samym sortowaniem, jeśli sortujesz dane wejściowe w miejscu.

Czy problem dystrybucji czekoladek jest problemem z oknem przesuwnym?

Tak, okno o stałym rozmiarze przesuwające się po posortowanych pakietach. W przeciwieństwie do okna z sumą bieżącą nie ma nic do aktualizowania podczas jego przesuwania: różnica dla każdego okna to wynik odejmowania pierwszego pakietu od ostatniego.

Czy problem z rozdzielaniem czekolady można rozwiązać bez sortowania?

Rozmiary są tutaj co najwyżej równe 10^5, więc sortowanie przez zliczanie porządkuje je w czasie O(n + 10^5) i obowiązuje to samo rozumowanie. Przy nieograniczonych rozmiarach same porównania nie pozwalają osiągnąć lepszego czasu niż O(n log n): dla m = 2 odpowiedź wynosi 0 dokładnie wtedy, gdy dwa pakiety są równe, a wykrycie duplikatu wymaga w najgorszym przypadku tylu porównań.

def minDifference(packets, m):
    # Napisz kod tutaj

Test #1

Test #2

Test #3

Argumenty

packets = [9, 3, 15, 7, 11, 4]
m = 3

Oczekiwany wynik