Effizientes Auswählen des Medians und der Elemente links und rechts davon

Angenommen, wir haben eine Menge von N Codierern.$S = \{ a_1,a_2,a_3,\ldots , a_N \}$$N$

Jeder Codierer hat die Bewertung und die Anzahl der Goldmedaillen E i , die er bisher gewonnen hat.$R_i$$E_i$

Ein Softwareunternehmen möchte genau drei Programmierer einstellen, um eine Anwendung zu entwickeln.

Für die Einstellung von drei Programmierern entwickelten sie die folgende Strategie:

1. Sie ordnen die Codierer zunächst in aufsteigender Reihenfolge der Bewertungen und absteigender Reihenfolge der Goldmedaillen an.
2. Aus dieser geordneten Liste wählen sie die drei mittleren Codierer aus. Wenn die geordnete Liste beispielsweise , wählen sie ( a 2 , a 3 , a 1 ) Codierer aus.$(a_5,a_2,a_3,a_1,a_4)$$(a_2,a_3,a_1)$

Jetzt müssen wir der Firma helfen, indem wir ein Programm für diese Aufgabe schreiben.

Eingang:

Die erste Zeile enthält , dh die Anzahl der Codierer.$N$

Dann wird die zweite Zeile enthält die Ratings des i - ten Codierer.$R_i$$i$

Die dritte Zeile enthält die Anzahl der Goldmedaillen, die vom ten Kodierer eingesackt wurden.$i$

Ausgabe:

Zeigen Sie nur eine Zeile an, die die Summe der Goldmedaillen der drei vom Unternehmen ausgewählten Codierer enthält.

Dies ist ein Problem des Auswählens des ten kleinsten Elements aus der Liste, das durch eine Klasse von Algorithmen gelöst wird, die Auswahlalgorithmen genannt werden . Es gibt deterministische Auswahlalgorithmen für die lineare Zeit, sodass Ihr Problem in linearer Zeit gelöst werden kann, indem Sie die n / 2 , n / 2 - 1 , n / 2 + 1 kleinsten Elemente aus der ursprünglichen unsortierten Liste auswählen .$k$$n/2,n/2-1,n/2+1$