Seleção eficiente da mediana e dos elementos à sua esquerda e direita

Suponha que tenhamos um conjunto de codificadores. $S = \{ a_1,a_2,a_3,\ldots , a_N \}$ $N$

Cada Codificador tem a classificação e o número de medalhas de ouro , que haviam ganho até agora. $R_i$ $E_i$

Uma empresa de software deseja contratar exatamente três codificadores para desenvolver um aplicativo.

Para a contratação de três codificadores, eles desenvolveram a seguinte estratégia:

Eles primeiro organizam os codificadores em ordem crescente de classificação e ordem decrescente de medalhas de ouro.
Nessa lista organizada, eles selecionam os três dos codificadores do meio. Por exemplo, se a lista organizada for eles selecionam codificadores. $(a_5,a_2,a_3,a_1,a_4)$ $(a_2,a_3,a_1)$

Agora temos que ajudar a empresa escrevendo um programa para esta tarefa.

Entrada:

A primeira linha contém , ou seja, o número de codificadores. $N$

Em seguida, a segunda linha contém as classificações do th codificador. $R_i$ $i$

A terceira linha contém o número de medalhas ensacados pelo th codificador. $i$

Resultado:

Exiba apenas uma linha que contenha a soma das medalhas de ouro conquistadas pelos três codificadores que a empresa selecionará.

algorithms algorithm-design Jack
fonte

Então codificadores de classificação mais alta sempre ganham menos medalhas? Caso contrário, que ordem você está realmente usando para classificar?

Jeffe

Respostas:

Esse é um problema de selecionar o menor elemento da lista resolvida por uma classe de algoritmos denominada Algoritmos de Seleção . Existem algoritmos de seleção de tempo linear determinístico para que seu problema possa ser resolvido em tempo linear, selecionando os menores elementos º da lista original não classificada. $k$ $n/2,n/2-1,n/2+1$

Optar
fonte

Se desejar, você pode executar o algoritmo de seleção uma vez para encontrar a mediana e, em seguida, encontrar o mínimo e o máximo nas partições direita e esquerda, respectivamente, de uma só vez.

Zach Langley

@Sid @ Zach Langley Oi, por favor, forneça o Pseudo-Código .i Passei pela paedia da wiki, mas me sinto um pouco difícil de entender.

Jack

@ Jack, você está familiarizado com o funcionamento do quicksort? O algoritmo de seleção aleatória é essencialmente o mesmo, exceto que apenas se repete em um lado de cada pivô.

Zach Langley

@Jack: O artigo da Wikipedia sobre algoritmos de seleção (vinculado na resposta de Sid) contém pseudocódigo. Google também funciona.

Jeffe

@Sid :: Eu li o algoritmo wiki (algoritmo de seleção geral baseado em partição) .Temos que chamar a função select três vezes com k = n / 2, k = n / 2-1, k / 2.Também, o que será o valor da esquerda, direita ao chamar a função select. Também na função de partição, qual será o valor do índice da partição.

Jack