Escrito por João Pedro Castro
Conhecimentos Prévios Necessários:
Quem fez essa questão foi muito generoso, pois existe várias maneiras de resolver ela. A mais comum eu imagino que tenha sido ordenar o vetor de maneira decrescente (maior para o menor), e imprimir a K-ésima posição. Essa é opção mais rápida, e acredito que a maioria tenha resolvido assim (incluindo eu). Mas, eu preferi tratar uma solução alternativa que não usa sort, e ela é bem legal também!
Perceba que para uma nota fixa é fácil checar se ela é uma nota válida ou não (possui no mínimo 
candidatos com a nota maior ou igual à ela). A complexidade disso, sem nenhuma otimização com outras técnicas, é 
. Só que perceba também que 
pelas restrições do enunciado, ou seja a resposta com certeza é uma dentre 100. Por tanto, tem como você só assumir que a resposta é 
, começando com 
, e toda vez que der errado você diminui em 1; e quando der certo você pode encerrar o loop e imprimir . E em no máximo 100 repetições você consegue uma resposta! Logo a complexidade final seria 
ou 
que são iguais no pior caso.