Binary Search the Answer – Bäume mit großem Abstand pflanzen

Angenommen, es gibt n mögliche Stellen, an denen ein Baum gepflanzt werden kann. Das Ziel ist, die Bäume so verteilt wie möglich zu pflanzen, damit sie sich in einigen Jahren nicht gegenseitig beeinträchtigen. Die Koordinaten dieser Stellen sind als ganze Zahlen gegeben.

Die Aufgabe besteht darin, den minimalen Abstand zwischen t Bäumen zu ermitteln, wenn man sie so weit auseinander wie möglich pflanzt.

Eingabe

Die erste Zeile der Eingabe enthält zwei ganze Zahlen n (1 ≤ n ≤ 100 000) – die Anzahl möglicher Stellen – und t (2 ≤ t ≤ n) – die Anzahl an Bäumen, die gepflanzt werden sollen.

Die nächste Zeile enthält n durch Leerzeichen getrennte unterschiedliche ganze Zahlen (0 ≤ ≤ ) – die Koordinaten der Stellen, an denen ein Baum gepflanzt werden kann.

Ausgabe

Das Programm soll den minimalen Abstand d zwischen den Bäumen ausgeben, wenn man sie so weit wie möglich auseinander setzt.

Beispiele

Eingabe	Ausgabe
5 3 1 2 8 4 9	3

Erklärung

Wir können die Bäume an den Koordinaten 1, 4 und 9 pflanzen ⇒ der minimale Abstand beträgt 4–1 = 3.

Tutorial

Diese Aufgabe lässt sich lösen, indem man eine Binärsuche auf das Ergebnis (den minimalen Abstand zwischen den Bäumen) durchführt. In jeder Iteration wird geprüft, ob es möglich ist, die Bäume mit einem bestimmten Mindestabstand zu platzieren. Für die Binärsuche auf das Ergebnis müssen einige wichtige Bedingungen erfüllt sein:

Es muss geprüft werden können, ob eine vorgeschlagene Antwort dem Problem genügt oder nicht (in unserem Fall: ob die Bäume bei einem vorgegebenen Mindestabstand d so gepflanzt werden können, dass sie mindestens d Einheiten auseinanderstehen).

Die Prüf-Funktion def check(x): soll True zurückgeben, falls die Platzierung aller Bäume mit Mindestabstand x machbar ist, andernfalls False.

Für wachsende Kandidatenwerte (verschiedene Werte von x) sollte das Ergebnis der Prüf-Funktion wie folgt aussehen:

False False False True True (impossible for the first several numbers and then possible for larger ones). In this case, we’re looking for the first True (the smallest valid value).
True True True True False False (possible for small numbers and impossible for larger ones). In this case, we’re looking for the last True (the largest valid value).

In our case, we would like to plant the trees as sparsely as possible. So, we would like the minimum distance to be as large as possible. If it’s possible to plant trees with a minimum distance of x, then it’s definitely possible to plan them denser and get a smaller x. Therefore, in our case, the values of the checking function will be True True True True False False and we aim to find the last True in this list (the largest (most sparse) minimal distance between the planted trees).

- False False False True True (zuerst ist es unmöglich, ab einem gewissen Punkt wird es möglich). In diesem Fall sucht man den ersten True (also den kleinsten gültigen Wert).

- True True True True False False (zuerst ist es möglich, ab einem bestimmten Punkt unmöglich). In diesem Fall sucht man den letzten True (also den größten gültigen Wert).

Unser Ziel ist ein möglichst großer Mindestabstand der Bäume. Wenn es möglich ist, Bäume mit Mindestabstand x zu platzieren, ist es auf jeden Fall auch möglich, sie enger zu setzen. Damit verhält sich die Prüf-Funktion wie True True True True False False und wir suchen den letzten True in dieser Reihe (also den größten Wert für den Mindestabstand).

n, t = ...
x = sorted(x)

def check(d):
    """ Prüft, ob wir 't' Bäume mit mindestens 'd' Einheiten Abstand pflanzen können """
    planted = 0               # Wir müssen t Bäume pflanzen (aktuell 0 gepflanzt)
    prev = float('-inf')      # Koordinate des zuletzt gepflanzten Baums
    for xi in x:
        if xi - prev >= d:    # Wenn wir an xi einen weiteren Baum pflanzen können
            planted += 1
            prev = xi
    return planted >= t

Mit dieser Prüf-Funktion lässt sich anschließend eine Binärsuche auf den Wert für den größtmöglichen Mindestabstand durchführen:

l, r = 1, max(x)         # Der mögliche Abstand liegt immer zwischen [l; r)
while r - l > 1:         # Es gibt zumindest einen Wert dazwischen, der geprüft werden kann
    mid = (l + r) // 2   # Wir nehmen den Mittelwert
    if check(mid):       # Wenn ein Abstand von mid möglich ist => l = mid
        l = mid
    else:                # Sonst setzen wir r = mid
        r = mid

print(l)

Binary Search the Answer – Bäume mit großem Abstand pflanzen

Eingabe

Ausgabe

Beispiele

Erklärung

Tutorial

Constraints

To check your solution you need to sign in

Sign in to continue