Эффективный выбор медианы и элементов слева и справа

Предположим, у нас есть множество из кодеров. $S = \{ a_1,a_2,a_3,\ldots , a_N \}$ $N$

Каждый кодер имеет рейтинг и количество золотых медалей , которые они выиграли до сих пор. $R_i$ $E_i$

Компания-разработчик программного обеспечения хочет нанять ровно трех программистов для разработки приложения.

Для найма трех кодеров они разработали следующую стратегию:

Сначала они размещают кодеров в порядке возрастания рейтингов и в порядке убывания золотых медалей.
Из этого упорядоченного списка они выбирают три средних кодера. Например, если упорядоченным списком является они выбирают кодеры. $(a_5,a_2,a_3,a_1,a_4)$ $(a_2,a_3,a_1)$

Теперь мы должны помочь компании, написав программу для этой задачи.

Входные данные:

Первая строка содержит $N$ , то есть количество кодеров.

Тогда вторая строка содержит рейтинги of $R_i$ $i$ - й кодер.

Третья строка содержит количество золотых медалей в мешки по $i$ го кодера.

Выход:

Выведите только одну строку, содержащую сумму золотых медалей, заработанных тремя кодировщиками, которые выберет компания.

algorithms algorithm-design разъем
источник

Так что кодеры с более высоким рейтингом всегда выигрывают меньше медалей? Если нет, то какой порядок вы используете для сортировки?

Джефф

Ответы:

$k$ $n/2,n/2-1,n/2+1$

выбирать
источник

Если вы хотите, вы можете запустить алгоритм выбора один раз, чтобы найти медиану, а затем найти минимум и максимум в правом и левом разделах соответственно одним махом.

Зак Лэнгли

@Sid @ Зак Лэнгли. Привет. Можете ли вы предоставить псевдокод. Я прошел через вики-педию, но немного сложнее понять. Так что вы можете предоставить псевдокод Спасибо большое!

Джек,

@ Джек, ты знаком с тем, как работает быстрая сортировка? Алгоритм рандомизированного выбора по сути тот же, за исключением того, что он повторяется только на одной стороне каждого центра.

Зак Лэнгли

@Jack: статья в википедии об алгоритмах выбора (ссылка на которую содержится в ответе Сида) содержит псевдокод. Гугл тоже работает.

Джефф

@Sid :: Я прочитал вики-алгоритм (общий алгоритм выбора на основе разделов). Нужно ли трижды вызывать функцию выбора с k = n / 2, k = n / 2-1, k / 2. Также что будет значение left, right при вызове функции select. Также в функции section, что будет значением индекса Index.

Джек,