Algorithmus in Python (Dichotomie)

Einführung

Ich war frei wegen des Einflusses des Koronavirus ... (unten weggelassen) Da der vorherige Seg-Baum schwer war, werde ich diesmal die Dichotomie zusammenfassen, die relativ einfach implementiert werden kann.

Denkweise

Wenn eine Grenze erfüllt ist und nicht erfüllt ist, können Sie mit ** O (logN) ** nach dieser Grenze suchen. Angenommen, Sie erhalten die folgende Liste mit ** x ** für diejenigen, die die Bedingungen nicht erfüllen, und ** o ** für diejenigen, die die Bedingungen erfüllen. 　　　　　　　　　　　xxxxxxoooooo

In Anbetracht des 0-Index ist die Dichotomie effektiv, wenn Sie den 5. oder 6. (entweder links oder rechts von der Grenze) finden möchten. Weisen Sie die linke Seite des Suchbereichs der Variablen ** links ** und die rechte Seite der Variablen ** rechts ** zu. Addiere diese und dividiere durch 2 (abgeschnitten) als ** mid **, um festzustellen, ob das Element mit dem Index ** mid ** die Bedingungen erfüllt. Wenn dies der Fall ist, gibt es rechts davon keine Begrenzung. Aktualisieren Sie daher den Wert von ** rechts ** auf ** mid ** und schneiden Sie die rechte Seite ab. Im Gegenteil, wenn es nicht erfüllt ist, gibt es links davon keine Grenze. Aktualisieren Sie daher den Wert von ** left ** auf ** mid **. Auf diese Weise wird der Abschnitt jedes Mal um die Hälfte verengt, und schließlich endet die Suche, wenn ** rechts ** und ** links ** nebeneinander liegen. Zu diesem Zeitpunkt hat ** rechts ** immer den Index des Elements, das die Bedingung erfüllt, und ** links ** hat den Index des Elements, das die Bedingung nicht erfüllt. Im obigen Beispiel ist ** links ** 5, ** rechts ** hat einen Wert von 6.

Beispiel 1

Betrachten Sie in ** [2, 5, 7, 9, 10, 18, 29] ** den kleinsten Index, der 9 oder mehr beträgt. Wenn die Bedingung 9 oder mehr ist, ist es ** xxxoooo **, ob sie erfüllt ist oder nicht, also ist die endgültige Antwort der Wert, den ** richtig ** hat.

Code

a = [2, 5, 7, 9, 10, 18, 29]

left = 0
right = len(a) - 1

while right - left > 1:
    mid = (right + left) // 2
    if a[mid] >= 9:
        right = mid
    else:
        left = mid

print(right) # 3

Beispiel 2

Da es eine große Sache ist, lösen Sie ** Kaufen Sie eine Ganzzahl ** von ABC146-C aus den früheren Fragen von atcoder. Für die Kandidaten 1 bis 10 ^ 9 gibt es eine Grenze, an der Sie die linke Seite und nicht die rechte Seite kaufen können. Sie sollten also in zwei Hälften suchen. Dieses Mal suchen wir direkt nach Ganzzahlen anstelle von Indizes. (Wenn Sie eine Liste erstellen, ist es TLE) Als Einschränkung gibt es keine Grenze, wenn Sie keine kaufen können und wenn Sie alle kaufen können. Daher scheint es besser, die Fälle zu trennen.

Code

import sys

a, b, x = [int(x) for x in input().split()]

left = 1
right = 10**9

if a*right + b*len(str(right)) <= x:
    print(right)
    sys.exit()

if a*left + b*len(str(left)) > x:
    print(0)
    sys.exit()

while right - left > 1:
    mid = (right + left) // 2
    if a*mid + b*len(str(mid)) <= x:
        left = mid
    else:
        right = mid

print(left)

Standardbibliothekshalbierung

Es kann zur Dichotomie verwendet werden, um festzustellen, ob es in der Liste enthalten ist, und um den Index zu finden, der das Element enthält, das Sie einfügen möchten. Sie können dies selbst machen, da es schon lange her ist von Ihnen selbst gemacht, aber es ist normal, ** bisect ** der Standardbibliothek zu verwenden. Überlegen. (Ich denke, es ist notwendig zu üben, wie man es benutzt)