Book Allocation Problem

Q: Czy problem przydziału książek jest taki sam jak problem podziału tablicy o największej sumie?

Tak. Oba sposoby dzielą tablicę na ustaloną liczbę niepustych, sąsiadujących bloków i minimalizują sumę największego bloku, a ten sam wyszukiwanie binarne z tym samym zachłannym sprawdzeniem rozwiązuje oba problemy. Wersja dotycząca książek dodaje przypadek -1 .

Q: Jaka jest złożoność czasowa problemu przydziału książek?

Czas O(n log S) i dodatkowa pamięć O(1) , gdzie n to liczba książek, a S to łączna liczba stron. Każdy testowany limit wymaga jednego przejścia po książkach, a wyszukiwanie sprawdza około log2 S limitów: 29 dla półki zawierającej 5 × 10^8 stron.

Q: Kiedy nie da się przydzielić książek?

Tylko wtedy, gdy uczniów jest więcej niż książek, ponieważ każdy uczeń potrzebuje co najmniej jednej książki. Jeśli książek jest wystarczająco dużo, dowolny stos złożony z dwóch lub więcej książek może oddać ostatnią książkę uczniowi, który nie ma żadnej, aż każdy będzie miał po jednej.

ŚrednieWyszukiwanie binarne Algorytmy zachłanne

+10

Na półce znajdują się książki w ustalonej kolejności, a pages[i] to liczba stron w książce i. Podziel książki między students uczniów: każdy uczeń otrzymuje jeden nieprzerwany ciąg sąsiadujących książek, co najmniej jedną książkę, a każda książka trafia dokładnie do jednego ucznia. Obciążenie ucznia to łączna liczba stron otrzymanych przez niego książek.

Zwróć najmniejszą możliwą wartość największego obciążenia. Jeśli uczniów jest więcej niż książek, zwróć -1.

Funkcja

allocateBooks(pages: integer-array, students: integer) → integer

pagesinteger-array: liczba stron każdej książki, w kolejności na półce
studentsinteger: liczba uczniów, którzy dzielą się książkami
Zwracainteger: najmniejszy możliwy największy ciężar lub -1, gdy liczba uczniów jest większa niż liczba książek

Ograniczenia

1 ≤ pages.length ≤ 5000
1 ≤ pages[i] ≤ 10⁵
1 ≤ students ≤ 10⁴
Zwróć -1, gdy students > pages.length.

Przykłady

Wejście: pages = [25, 40, 15, 30, 50]students = 3
Wyjście: 65
Wyjaśnienie: Rozdaj [25, 40], [15, 30] i [50]: obciążenia wynoszą 65, 45 i 50. Limit 64 nie wystarcza: podział daje [25], [40, 15], [30], [50], czyli czterech uczniów.

Wejście: pages = [10, 20]students = 3
Wyjście: -1
Wyjaśnienie: Dwie książki nie wystarczą, aby trzech uczniów dostało po jednej książce, więc odpowiedzią jest -1.

Pytanie dodatkowe

Udowodnij, że średni udział, zaokrąglony w górę, plus najgrubsza książka zawsze stanowi działającą granicę. Ile sprawdzeń pozwala zaoszczędzić ta górna granica na półce z cienkimi książkami?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Istnieje zbyt wiele sposobów na podzielenie półki, ale sprawdzenie jednego limitu stron jest tanie: rozdawaj książki w kolejności na półce, przechodząc do następnego ucznia, gdy kolejna książka przekroczyłaby limit, i policz uczniów. Wyższy limit nigdy nie wymaga większej liczby uczniów, więc działające limity tworzą jeden ciąg, a wyszukiwanie binarne pozwala znaleźć jego początek.

Zwiększaj limit stron po jednej stronie

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

Intuicja

Zacznij od L = max(pages), ponieważ ktoś ma najgrubszą książkę, i zwiększaj L o jedną stronę, aż liczba wyznaczona metodą zachłanną zmieści się w students. Każdy niższy limit nie spełniał warunku, więc pierwszy, który go spełnia, jest odpowiedzią. W pierwszym przykładzie każdy limit od 50 do 64 wymaga czterech uczniów, a 65 wymaga trzech: 16 sprawdzeń.

Odpowiedzią może być cała półka: jeden uczeń i 5000 książek po 10^5 stron oznaczają około 5 × 10^8 limitów, z których każdy wymaga przejrzenia 5000 książek. W kolumnie czasu A oznacza odpowiedź, a m — najgrubszą książkę.

Algorytm

Jeśli students > pages.length, zwróć -1.
Zapisz zachłanny sposób liczenia dla limitu L: zacznij od jednego studenta i obciążenia równego 0; gdy load + pages[i] > L, dodaj studenta i ustaw obciążenie na pages[i], w przeciwnym razie dodaj książkę do obciążenia.
Ustaw L na grubość najgrubszej książki.
Gdy liczba dla L jest większa niż students, zwiększ L o 1.
Zwróć L.

def studentsNeeded(pages, limit):
    count, load = 1, 0  # the first student starts with no pages
    for p in pages:
        if load + p > limit:
            count += 1  # this book opens the next student's block
            load = p
        else:
            load += p
    return count


def allocateBooks(pages, students):
    if students > len(pages):
        return -1  # someone would get no book
    limit = max(pages)  # the thickest book has to fit somewhere
    while studentsNeeded(pages, limit) > students:
        limit += 1
    return limit

Wyszukiwanie binarne przy limicie strony

Intuicja

Chciwa liczba to najmniejsza liczba uczniów, jaką może wykorzystać dowolny podział przy L. Porównując każdego ucznia z osobna z dowolnym innym podziałem, każdy uczeń w podziale zachłannym zatrzymuje się dopiero wtedy, gdy następna książka się nie mieści, więc kończy co najmniej tak daleko na półce. Mniejsza liczba uczniów, niż masz do dyspozycji, nie stanowi problemu: uczeń mający dwie książki może przekazać jedną uczniowi, który nie ma żadnej, a żadne obciążenie nie wzrośnie.

Zatem L działa dokładnie wtedy, gdy chciwa liczba jest nie większa niż students. Każdy podział działający przy L działa również przy L+1, więc wyszukiwanie binarne znajduje pierwszy działający limit.

Zakres zaczyna się od większej z wartości max(pages) i średniego przydziału, czyli total / students zaokrąglonego w górę, ponieważ największe obciążenie jest co najmniej równe obu tym wartościom. Górną granicą jest total. W pierwszym przykładzie zakres wynosi od 54 do 160, a wyszukiwanie sprawdza kolejno 107, 80, 67, 60, 64, 66 i 65.

Algorytm

Jeśli students > pages.length, zwróć -1.
Dodaj wartości total i znajdź najgrubszą książkę. Ustaw lo na większą z wartości: grubość najgrubszej książki oraz (total + students - 1) / students, a hi = total.
Gdy lo < hi, oblicz mid = lo + (hi - lo) / 2.
Wykonaj zachłanne zliczanie dla mid. Jeśli wynik jest nie większy niż students, ustaw hi = mid; w przeciwnym razie ustaw lo = mid + 1.
Zwróć lo.

def studentsNeeded(pages, limit):
    count, load = 1, 0  # the first student starts with no pages
    for p in pages:
        if load + p > limit:
            count += 1  # this book opens the next student's block
            load = p
        else:
            load += p
    return count


def allocateBooks(pages, students):
    if students > len(pages):
        return -1  # someone would get no book
    total = sum(pages)
    # no limit can be below the thickest book or below the average share
    lo = max(max(pages), (total + students - 1) // students)
    hi = total  # one student could carry the whole shelf
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if studentsNeeded(pages, mid) <= students:
            hi = mid  # mid is enough, so the answer is mid or lower
        else:
            lo = mid + 1  # mid needs too many students
    return lo

Pułapki i przypadki brzegowe

Pominięcie sprawdzenia -1. Dla [10, 20] i 3 uczniów zachłanny algorytm przy limicie 20 przydziela książki 2 uczniom, więc wyszukiwanie zwraca 20.
Rozpoczęcie zakresu od samej średniej liczby stron przypadających na ucznia. Dla [1, 9] i 2 uczniów średnia wynosi 5, a zachłanny algorytm przydziela uczniowi książkę z 9 stronami, zlicza 2 uczniów i zwraca 5.
Sprawdzanie, czy liczba uczniów wynosi dokładnie students. Dla [5, 5, 5, 5, 5, 5] i 4 uczniów odpowiedź wynosi 10, a zachłanny algorytm zlicza 3 uczniów.
Sortowanie książek. Dla [10, 1, 1, 10] i 2 uczniów wynik wynosi 11, ale po posortowaniu do [1, 1, 10, 10] wynosi 12.

Najczęstsze pytania3

Czy problem przydziału książek jest taki sam jak problem podziału tablicy o największej sumie?

Tak. Oba sposoby dzielą tablicę na ustaloną liczbę niepustych, sąsiadujących bloków i minimalizują sumę największego bloku, a ten sam wyszukiwanie binarne z tym samym zachłannym sprawdzeniem rozwiązuje oba problemy. Wersja dotycząca książek dodaje przypadek -1.

Jaka jest złożoność czasowa problemu przydziału książek?

Czas O(n log S) i dodatkowa pamięć O(1), gdzie n to liczba książek, a S to łączna liczba stron. Każdy testowany limit wymaga jednego przejścia po książkach, a wyszukiwanie sprawdza około log2 S limitów: 29 dla półki zawierającej 5 × 10^8 stron.

Kiedy nie da się przydzielić książek?

Tylko wtedy, gdy uczniów jest więcej niż książek, ponieważ każdy uczeń potrzebuje co najmniej jednej książki. Jeśli książek jest wystarczająco dużo, dowolny stos złożony z dwóch lub więcej książek może oddać ostatnią książkę uczniowi, który nie ma żadnej, aż każdy będzie miał po jednej.

def allocateBooks(pages, students):
    # Wpisz kod tutaj

Test #1

Test #2

Test #3

Argumenty

pages = [25, 40, 15, 30, 50]
students = 3

Oczekiwany wynik