Aggressive Cows

Q: Jaka jest złożoność czasowa problemu Aggressive Cows?

Sortowanie zajmuje O(n log n) , a wyszukiwanie binarne O(n log D) , gdzie D to rozpiętość między stanowiskami podzielona przez k-1 . Poza posortowaną kopią pamięć wynosi O(1) .

Q: Dlaczego pierwsza krowa zawsze trafia do skrajnego lewego boksu?

Wybierz dowolne rozmieszczenie, które spełnia warunki, i przesuń jego skrajną lewą krowę do skrajnego lewego boksu. Ta krowa oddala się tylko od pozostałych, więc żadna odległość się nie zmniejsza, a w pewnym optymalnym rozmieszczeniu wykorzystany jest skrajny lewy boks.

Q: Jak rozpoznać wyszukiwanie binarne po odpowiedzi?

Pytanie dotyczy największej lub najmniejszej wartości, dla której coś jest możliwe. Sprawdzenie jednej wartości jest znacznie łatwiejsze niż znalezienie najlepszej, a odpowiedzi zmieniają się tylko raz, gdy wartość rośnie. Tutaj wartością jest odstęp, a sprawdzeniem — zachłanne rozmieszczanie.

ŚrednieWyszukiwanie binarne Sortowanie Algorytmy zachłanne

+10

Stodoła ma boksy rozmieszczone wzdłuż jednej prostej, a stalls[i] to pozycja boksu i. Wszystkie pozycje są różne i nie są uporządkowane w szczególny sposób. Musisz umieścić k krów w k różnych boksach. Krowy walczą, gdy stoją blisko siebie, dlatego chcesz, aby dwie najbliżej siebie stojące krowy były jak najdalej od siebie.

Zwróć największą możliwą wartość najmniejszej odległości między dowolnymi dwiema krowami.

Funkcja

aggressiveCows(stalls: integer-array, k: integer) → integer

stallsinteger-array: różne pozycje postojowe, w dowolnej kolejności
kinteger: liczba krów do umieszczenia
Zwracainteger: największa możliwa najmniejsza odległość między dwiema krowami

Ograniczenia

2 ≤ stalls.length ≤ 5000
0 ≤ stalls[i] ≤ 10⁹
Wszystkie pozycje w stalls są różne.
2 ≤ k ≤ stalls.length

Przykłady

Wejście: stalls = [10, 1, 7, 4, 15]k = 3
Wyjście: 6
Wyjaśnienie: Krowy na pozycjach 1, 7 i 15 stoją w odległości 6 i 8 od siebie. Odległość 7 nie spełnia warunku: po krowie na pozycji 1 następna trafia na pozycję 10, a żadna zagroda nie znajduje się na pozycji 17 ani dalej.

Pytanie dodatkowe

Co się zmienia, jeśli stoiska stoją na okręgu, tak że ostatnie stoisko w kolejności jest również sąsiadem pierwszego?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Ustal odstęp i zapytaj: czy k krów może stanąć tak, by każda para była oddalona od siebie co najmniej o tę odległość? Odpowiedź uzyskasz w jednym zachłannym przejściu po posortowanych stanowiskach. Wraz ze wzrostem odstępu odpowiedź zmienia się raz z „tak” na „nie”, więc wyszukiwanie binarne znajduje ostatnie „tak”.

Sortuj, a następnie kolejno sprawdzaj każdą lukę

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

Intuicja

Posortuj pozycje. Dwie najbliższe krowy są wtedy zawsze sąsiadami, więc odstęp g jest odpowiedni, gdy każda para sąsiadujących krów jest oddalona od siebie o co najmniej g.

Aby sprawdzić odstęp, umieść krowę w skrajnym lewym boksie, a następnie kolejną w każdym boksie oddalonym o co najmniej g od ostatniej krowy. To zachłanne rozmieszczenie mieści tyle krów, ile może pomieścić każde rozmieszczenie. Ustaw dowolne poprawne rozmieszczenie od lewej strony: krowa i w rozmieszczeniu zachłannym nigdy nie znajduje się na prawo od krowy i w tamtym rozmieszczeniu, więc algorytm zachłanny znajduje boks dla następnej krowy nie później.

Odstęp 1 zawsze jest odpowiedni, więc próbuj g = 2, 3, ... i zakończ przy pierwszym odstępie, przy którym można rozmieścić mniej niż k krów. W pierwszym przykładzie odstęp 6 pozwala rozmieścić 3 krowy, a odstęp 7 tylko 2, więc odpowiedź to 6.

Przy dwóch krowach i boksach na pozycjach 0 i 10^9 oznacza to około 10^9 przejść przez 5000 boksów, czyli 5 × 10^12 kroków.

Algorytm

Posortuj pozycje.
Napisz sprawdzanie odstępu g: jedna krowa na pos[0], a następnie krowa w każdym boksie, w którym pos[i] - last ≥ g, zliczając krowy.
Zacznij od gap = 1.
Gdy sprawdzanie dla gap + 1 pozwala umieścić co najmniej k krów, zwiększ gap o 1.
Zwróć gap.

def cowsPlaced(pos, gap):
    count, last = 1, pos[0]  # the first cow takes the leftmost stall
    for p in pos[1:]:
        if p - last >= gap:
            count += 1
            last = p
    return count


def aggressiveCows(stalls, k):
    pos = sorted(stalls)
    gap = 1  # positions are distinct, so a gap of 1 always fits every cow
    while cowsPlaced(pos, gap + 1) >= k:
        gap += 1
    return gap

Wyszukiwanie binarne w luce

Intuicja

Rozmieszczenie, w którym każda przerwa ma długość co najmniej g+1, ma też każdą przerwę o długości co najmniej g, więc wyniki sprawdzeń to tak, ..., tak, nie, ..., nie. Wyszukiwanie binarne znajduje ostatnie „tak”.

Rozpocznij wyszukiwanie od lo = 1, które zawsze działa, oraz od hi = rozpiętość podzielona przez k-1, zaokrąglona w dół: k krów tworzy k-1 przerw w obrębie rozpiętości, więc najmniejsza przerwa nie może być większa. Jeśli sprawdzenie się powiedzie, ustawiamy lo = mid, więc mid trzeba zaokrąglać w górę; przy zaokrąglaniu w dół lo = 5 i hi = 6 będą się powtarzać w nieskończoność.

W pierwszym przykładzie rozpiętość wynosi 14, a k = 3, więc hi = 7. Przerwa 4 przechodzi sprawdzenie, przerwa 6 przechodzi sprawdzenie, przerwa 7 nie przechodzi, a zakres zawęża się do 6.

Zakres o szerokości do 10^9 zawęża się w około 30 sprawdzeniach po 5000 stanowisk, czyli w przybliżeniu 150 000 krokach.

Algorytm

Posortuj pozycje.
Ustaw lo = 1 i hi = (pos[n-1] - pos[0]) / (k-1), zaokrąglając w dół.
Gdy lo < hi, oblicz mid = lo + (hi - lo + 1) / 2.
Jeśli zachłanne sprawdzenie dla mid pozwala umieścić co najmniej k krów, ustaw lo = mid; w przeciwnym razie ustaw hi = mid - 1.
Zwróć lo.

def cowsPlaced(pos, gap):
    count, last = 1, pos[0]  # the first cow takes the leftmost stall
    for p in pos[1:]:
        if p - last >= gap:
            count += 1
            last = p
    return count


def aggressiveCows(stalls, k):
    pos = sorted(stalls)
    lo = 1  # positions are distinct, so a gap of 1 always works
    hi = (pos[-1] - pos[0]) // (k - 1)  # k-1 gaps share the whole span
    while lo < hi:
        mid = lo + (hi - lo + 1) // 2  # round up so lo = mid always moves
        if cowsPlaced(pos, mid) >= k:
            lo = mid  # mid fits, so the answer is mid or larger
        else:
            hi = mid - 1  # mid does not fit, so the answer is smaller
    return lo

Pułapki i przypadki brzegowe

Pominięcie sortowania. Dla nieposortowanej tablicy [10, 1, 7, 4, 15] i odstępu 6 sprawdzanie zaczyna się od 10, nie znajduje późniejszego stanowiska oddalonego od niego o co najmniej 6 i podaje, że można umieścić jedną krowę.
Zaokrąglanie mid w dół, gdy w przebiegu ustawiana jest wartość lo = mid. Gdy hi = lo + 1, zakres przestaje się zmniejszać i pętla nigdy się nie kończy.
Sprawdzanie, czy liczba krów wynosi dokładnie k. Przy odstępie 1 w pierwszym przykładzie można umieścić 5 krów, czyli więcej niż 3, a odstęp nadal się sprawdza; testuj count ≥ k.
Rozpoczynanie liczenia krów od 0. Krowa w skrajnym lewym stanowisku też się liczy, więc liczenie zaczyna się od 1.

Najczęstsze pytania3

Jaka jest złożoność czasowa problemu Aggressive Cows?

Sortowanie zajmuje O(n log n), a wyszukiwanie binarne O(n log D), gdzie D to rozpiętość między stanowiskami podzielona przez k-1. Poza posortowaną kopią pamięć wynosi O(1).

Dlaczego pierwsza krowa zawsze trafia do skrajnego lewego boksu?

Wybierz dowolne rozmieszczenie, które spełnia warunki, i przesuń jego skrajną lewą krowę do skrajnego lewego boksu. Ta krowa oddala się tylko od pozostałych, więc żadna odległość się nie zmniejsza, a w pewnym optymalnym rozmieszczeniu wykorzystany jest skrajny lewy boks.

Jak rozpoznać wyszukiwanie binarne po odpowiedzi?

Pytanie dotyczy największej lub najmniejszej wartości, dla której coś jest możliwe. Sprawdzenie jednej wartości jest znacznie łatwiejsze niż znalezienie najlepszej, a odpowiedzi zmieniają się tylko raz, gdy wartość rośnie. Tutaj wartością jest odstęp, a sprawdzeniem — zachłanne rozmieszczanie.

def aggressiveCows(stalls, k):
    # Wpisz kod tutaj

Test #1

Test #2

Test #3

Argumenty

stalls = [10, 1, 7, 4, 15]
k = 3

Oczekiwany wynik