Es ist leicht zu vergessen, wie die Dichotomiefunktion in der Wettbewerbsprogrammierung verwendet wird, daher werde ich sie als Memorandum aufbewahren. Bitte beachten Sie auch, dass dieser Artikel nicht beschreibt, wie eine Dichotomie aussieht. Bitte beachten Sie außerdem, dass dieser Artikel die ** Grundverwendung ** bestätigen soll.
In Python verarbeitet das Halbierungsmodul Funktionen im Zusammenhang mit der Dichotomie. Dieses Modul unterstützt das Arbeiten mit ** (aufsteigender) sortierter Liste ** in der angegebenen Reihenfolge.
In der Wettbewerbsprogrammierung werden hauptsächlich die folgenden zwei Funktionen verwendet. Im Folgenden ist das zu untersuchende Element x, die zu untersuchende ** (aufsteigende) sortierte Liste ** ist a, das erste Argument ist a und das zweite Argument ist x. Der in a zu untersuchende Bereich kann im 3. und 4. Argument angegeben werden, wird hier jedoch nicht behandelt. Siehe Bisect-Modul.
①bisect_left Gibt den Index der Einfügemarke auf a ganz links von x zurück (in der angegebenen Reihenfolge). $ \ leftrightarrow Gibt den Index des kleinsten Elements über $ x zurück. $ \ leftrightarrow $ Das Element links ist das größte (Index-) Element, das kleiner als x ist.
②bisect_right Gibt den Index der Einfügemarke auf a ganz rechts von x zurück (in der angegebenen Reihenfolge). $ \ leftrightarrow Gibt den Index des kleinsten Elements zurück, das größer als $ x ist. $ \ leftrightarrow $ Das Element links ist das größte (Index-) Element unter x.
In C ++ verarbeitet die Algorithmusbibliothek Funktionen im Zusammenhang mit der Dichotomie. In dieser Bibliothek ** funktioniert jede Datenstruktur, wenn Sie einen Iterator haben, der die Anforderungen des Algorithmus erfüllt **.
In der Wettbewerbsprogrammierung werden hauptsächlich die folgenden zwei Funktionen verwendet. Außerdem sei x wie zuvor das Element, das Sie überprüfen möchten, und a das ** (aufsteigend) sortierte Array **, das überprüft werden soll. Geben Sie zu diesem Zeitpunkt den zu untersuchenden Bereich mit dem ersten Argument als a.begin () und dem zweiten Argument als a.end () an und geben Sie das zu untersuchende Element x im dritten Argument an.
①lower_bound Synonym für Pythons bisect_left, gibt jedoch das kleinste Element ** iterator ** mit Elementen zurück, die größer oder gleich x sind. Wenn Sie den minimalen ** Index ** erhalten möchten, können Sie ihn auch mit (Rückgabewert) -a.begin () abrufen.
②upper_bound Synonym für Pythons bisect_right, gibt jedoch den ** Iterator ** des kleinsten Elements zurück, das größer als x ist. Wenn Sie den minimalen ** Index ** erhalten möchten, können Sie ihn auch mit (Rückgabewert) -a.begin () abrufen.
✳︎ Aufsteigende Reihenfolge Eine sortierte Liste ist erforderlich, kann jedoch auch dann sortiert werden, wenn sie nicht in aufsteigender Reihenfolge vorliegt, indem der Operator überlastet wird. ✳︎ Wenn Sie mehr über C ++ Lower_bound und Upper_bound erfahren möchten, lesen Sie bitte diesen Artikel. ✳︎ Wenn Sie weitere wichtige Dinge haben, teilen Sie uns dies bitte in den Kommentaren mit!
Recommended Posts