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

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

Każdy Coders ma ocenę liczbę złotych medali , 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ę:

Najpierw układają kodery w kolejności rosnącej i malejącej względem złotych medali.
Z tej uporządkowanej listy wybierają trzy środkowe kodery. Na przykład, jeśli lista jest umieszczony wybierają 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 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.

algorithms algorithm-design

— Jacek
źródło

Więc wyżej oceniani koderzy zawsze zdobywają mniej medali? Jeśli nie, to jakiej kolejności faktycznie używasz do sortowania?

— JeffE

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 najmniejsze elementy z oryginalnej nieposortowanej listy. $k$ $n/2,n/2-1,n/2+1$

— Optować
źródło

Jeśli chcesz, możesz raz uruchomić algorytm wyboru, aby znaleźć medianę, a następnie znaleźć minimum i maksimum w prawej i lewej partycji odpowiednio za jednym zamachem.

— Zach Langley,

@Sid @ Zach Langley Cześć, czy możesz podać kod pseudo. Przeszedłem przez wiki paedia, ale wydaje się to trudne do zrozumienia. Więc możesz podać kod pseudo Dziękujemy bardzo!

— Jack

@Jack Czy wiesz, jak działa Quicksort? Algorytm losowego wyboru jest zasadniczo taki sam, z tym wyjątkiem, że powtarza się tylko po jednej stronie każdej osi obrotu.

— Zach Langley,

@Jack: Artykuł w Wikipedii na temat algorytmów wyboru (połączony w odpowiedzi Sida) zawiera pseudokod. Google również działa.

— JeffE

@Sid :: Czytam algorytm wiki (ogólny algorytm selekcji oparty na partycjach). Czy musimy trzy razy wywoływać funkcję wyboru z k = n / 2, k = n / 2-1, k / 2. Również to, co będzie wartość left, right podczas wywoływania funkcji select. Również w funkcji partycji, jaka będzie wartość indeksu partycji.

— Jack