beecrowd 1766 · Ordenação multicritério

O Elfo das Trevas

Cada rena possui nome, peso, idade e altura. Precisamos produzir um ranking e selecionar apenas as primeiras posições solicitadas.

Enunciado Código .py

Registro

(nome, peso, idade, altura) para cada rena.

Prioridade

Maior peso; depois menor idade, menor altura e menor nome.

Saída

Cabeçalho do cenário e somente as primeiras puxar renas.

Uma chave substitui vários if

O Python compara tuplas da esquerda para a direita. Assim que encontra campos diferentes, a decisão está tomada e os campos seguintes deixam de importar.

O sinal negativo resolve o peso: como sort é crescente, -110 aparece antes de -90. Isso equivale a ordenar o peso original em ordem decrescente.

Mapa da solução

Leia cada registro

Converta peso e idade para inteiro e altura para ponto flutuante.

Crie uma chave composta

(-peso, idade, altura, nome) codifica todas as prioridades.

Ordene os registros completos

A chave decide a posição, mas a tupla inteira da rena é movimentada.

Recorte o ranking

O laço percorre somente os índices de 0 até puxar - 1.

Execução interativa

Ranking por chave composta

comparação

Ordem dos critérios

1Pesodecrescente
2Idadecrescente
3Alturacrescente
4Nomecrescente

Por que existem empates?

A amostra possui pesos, idades e alturas repetidos para obrigar a comparação a avançar até critérios posteriores.

Quantidade escolhida: puxar = 3.

Ranking em construção

vermelho: comparação · verde no final: selecionada
#NomePesoIdadeAlturaChave usada
Quem está sendo inserida
Quem está sendo comparada
Ordem atual

Visualização e código real

A animação usa Insertion Sort apenas para tornar cada comparação visível. Sua solução chama list.sort(), que no Python usa Timsort. Os algoritmos internos são diferentes, mas obedecem exatamente à mesma chave e produzem o mesmo ranking.

sort() movimenta as tuplas dentro da própria lista. Depois disso, o laço de saída não precisa comparar nada: ele apenas pega o prefixo solicitado.

Código completo comentado 
quantidade_de_cenarios = int(input())

for numero_do_cenario in range(1, quantidade_de_cenarios + 1):
    quantidade_de_renas, quantidade_escolhida = map(int, input().split())
    renas = []

    for _ in range(quantidade_de_renas):
        nome, peso, idade, altura = input().split()

        # A tupla mantém os quatro dados da rena no mesmo registro.
        renas.append((nome, int(peso), int(idade), float(altura)))

    # Chave: peso decrescente, idade crescente,
    # altura crescente e nome crescente.
    renas.sort(
        key=lambda rena: (
            -rena[1],
            rena[2],
            rena[3],
            rena[0],
        )
    )

    print(f"CENARIO {{{numero_do_cenario}}}")

    # A lista ordenada é o ranking; imprimimos apenas o prefixo pedido.
    for posicao, rena in enumerate(renas[:quantidade_escolhida], start=1):
        print(f"{posicao} - {rena[0]}")

Complexidade

Para m renas, a ordenação custa O(m log m) no caso geral. Construir as chaves custa O(m), e imprimir as primeiras p posições custa O(p). A lista de registros ocupa O(m).