Skutecznie wybierając medianę i elementy po jej lewej i prawej stronie

Załóżmy, że mamy do zestawu na N koderów.$S = \{ a_1,a_2,a_3,\ldots , a_N \}$$N$

Każdy Coders ma ocenę liczbę złotych medali E i , które do tej pory zdobyli.$R_i$$E_i$

Firma programistyczna chce zatrudnić dokładnie trzech programistów do opracowania aplikacji.

Aby zatrudnić trzech programistów, opracowali następującą strategię:

1. Najpierw układają kodery w kolejności rosnącej i malejącej względem złotych medali.
2. Z tej uporządkowanej listy wybierają trzy środkowe kodery. Na przykład, jeśli lista jest umieszczony wybierają ( 2 , 3 , A 1 ) koderów.$(a_5,a_2,a_3,a_1,a_4)$$(a_2,a_3,a_1)$

Teraz musimy pomóc firmie, pisząc program do tego zadania.

Wejście:

Pierwszy wiersz zawiera , tj. Liczbę koderów.$N$

Potem drugi wiersz zawiera wskaźniki od I th koder.$R_i$$i$

Trzecia linia zawiera liczbę złotych medali zgromadzonych przez tego programistę.$i$

Wynik:

Wyświetl tylko jedną linię, która zawiera sumę złotych medali zdobytych przez trzech programistów, których wybierze firma.

Jest to problem wyboru tego najmniejszego elementu z listy, rozwiązany przez klasę algorytmów zwanych Algorytmami Selekcji . Istnieją deterministyczne algorytmy liniowego wyboru czasu, dzięki czemu problem można rozwiązać w czasie liniowym, wybierając n / 2 , n / 2 - 1 , n / 2 + 1 najmniejsze elementy z oryginalnej nieposortowanej listy.$k$$n/2,n/2-1,n/2+1$