Die Erklärung mit Multiset wurde im E-Problem des AtCoder Beginner Contest geschrieben, aber ich denke, dass es Sprachen wie Python gibt, die kein Mutiset haben. Daher möchte ich einen alternativen Algorithmus mit Priority Queue (heapq) einführen. Ich werde das Problem selbst nicht erklären, also lesen Sie bitte die offizielle Erklärung dort.
ABC170 E - Smart Infants https://atcoder.jp/contests/abc170/tasks/abc170_e
multiset Intern [Dichotomiebaum](https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2%E6%9C % A8) wird verwendet. Dadurch bleiben die Daten jederzeit sortiert, anstatt jedes Mal, wenn Daten eingefügt werden, O (logN) zu verwenden. Daher ist es möglich, mit O (logN) zu löschen und zu suchen. Wenn Sie den Dichotomiebaum selbst implementieren, können Sie ihn in Sprachen verwenden, die nicht als Standard bereitgestellt werden, aber Sie müssen ihn entwickeln, um das Gleichgewicht zu halten. (Beispiel für Einfallsreichtum: [Tree Master Training Course] 7-1. Was ist Splay Tree? Erläuterung [Competition Pro Katsuppa])
Priority Queue Intern in GCC [Dichotomie](https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E3%83%92%E3%83%BC%E3%83 % 97) wird verwendet. Dieselbe Datenstruktur wird intern in Heapq von Python verwendet. Das Einfügen von Daten erfordert jedes Mal O (logN), wie der Dichotomiebaum. Da es sich um einen Heap-Baum handelt, ist das Innere ** nicht sortiert, und Sie können mit hoher Geschwindigkeit nichts anderes als den Maximalwert (Minimalwert) suchen oder löschen **, aber Sie können den Maximalwert (Minimalwert) nicht immer mit dem Berechnungsbetrag O (1) erhalten. Ich kann es schaffen Der Vorteil gegenüber dem Dichotomiebaum besteht darin, dass der Rechenaufwand stabil ist, da das Gleichgewicht immer ohne besonderen Einfallsreichtum aufrechterhalten wird.
In dieser Angelegenheit
Es wäre schön, wenn dies immer mit hoher Geschwindigkeit möglich wäre.
Wie im offiziellen Kommentar erwähnt, kann jeder Prozess mit Multiset mit hoher Geschwindigkeit ausgeführt werden. Da der vierte Prozess jedoch mit Priority Queue nicht mit hoher Geschwindigkeit ausgeführt werden kann, muss die Denkweise geändert werden.
Beachten Sie bei der Lösung dieses Problems, dass die vierte Bedingung ** nicht unbedingt ein Prozess ist, der ausgeführt werden muss, es sei denn, sie stört die erste und die zweite Bedingung **. Mit anderen Worten, auch wenn es nicht tatsächlich aus den Daten gelöscht wird, spielt es keine Rolle, ob der Maximalwert des festgelegten Satzes und der Minimalwert des in jedem Kindergarten festgelegten Höchstsatzes nicht betroffen sind.
Da sich die Implementierung unter den ersten und zweiten Bedingungen nicht ändert (das Maximum und das Minimum werden umgedreht), wird die erste Bedingung (Erhalten des Maximalwerts der Menge) als Beispiel erläutert.
Betrachten Sie nun zwei Prioritätswarteschlangen.
Und ** fügen Sie das Element in 1 ein, wenn Sie den Park betreten, und in 2, wenn Sie den Park ändern. Wenn die Maxima von 1 und 2 gleich sind, entfernen Sie sie von beiden. ** ** ** Dies stellt sicher, dass der Maximalwert für diesen Kindergarten immer dem Maximalwert für 1 entspricht.
Ich werde hier Code einfügen, aber es funktioniert nicht, auch wenn ich ihn je nach Umgebung kopiere, da Standard und Include fehlerhaft sind.
Code.cpp
priority_queue<int> in;
priority_queue<int> out;
//Bearbeitung beim Betreten des Parks
void infant_in(int i){
in.push(i);
}
//Verarbeitung beim Gartenwechsel
void infant_out(int i){
out.push(i);
while(!out.empty() && in.top() == out.top()){
in.pop();
out.pop();
}
}
//Holen Sie sich das Maximum
int get_max(){
return in.top();
}
Schauen wir uns ein konkretes Beispiel an. Bedenken Sie, dass Kinder mit einer Rate von 3,5,8 den Kindergarten betreten und Kinder mit einer Rate von 5,8 sich in dieser Reihenfolge bewegen.
>Drei Kindergartenkinder treten ein
Tatsächlicher Kindergarten= {3,5,8}
1 = [3,5,8] 2 = [] #Natürlich ist der Maximalwert an dieser Stelle 8
>Kinder mit einer Rate von 5 werden übertragen
Tatsächlicher Kindergarten= {3,8}
1 = [3,5,8] 2 = [5] #Der Maximalwert beträgt 8
>Kinder mit einer Rate von 8 werden übertragen
Tatsächlicher Kindergarten= {3}
1 = [3,5,8] 2 = [5,8]
1 = [3,5] 2 = [5]
1 = [3] 2 = [] #Der Maximalwert ist 3
Mit dieser Art von Gefühl können Sie sehen, dass es kein Problem ist, den Maximalwert zu erreichen.
Es ist ein Berechnungsbetrag, um den man sich Sorgen machen muss, aber da die Häufigkeit, mit der der Wert von innen und außen gelöscht wird, die bei diesem Problem als Engpass erscheint, maximal Q-mal beträgt, kann er ignoriert werden, und der Berechnungsbetrag ist O (NlogN), der beim Einfügen des Werts erforderlich ist. Werden. Das ist schnell genug.
Recommended Posts