Solução escrita por Malu Azevedo
Conhecimentos necessários:
O problema nos pede para encontrar a quantidade mínima de cabos necessária (1, 2 ou 3) para obter um comprimento total maior ou igual a , considerando que ao amarrar dois cabos perdemos 10 cm nos nós. Se não for possível nem com 3 cabos, devemos imprimir -1.
Ideia Central
Para encontrar a quantidade mínima de cabos necessária para atingir ou superar o comprimento , percebemos que para formar a maior soma possível com 1, 2 ou 3 cabos, devemos sempre escolher os maiores cabos disponíveis no depósito. Assim, não precisamos ordenar todos os elementos; basta mantermos os três maiores comprimentos encontrados durante a leitura dos dados. Se o maior cabo sozinho for suficiente, a resposta é 1. Caso contrário, se a soma dos dois maiores cabos (descontando 10 cm do nó) atingir , a resposta é 2. Se a soma dos três maiores cabos (descontando 20 cm dos nós) for suficiente, a resposta é 3. Caso nenhuma dessas opções atinja o valor desejado, é impossível resolver o problema, retornando -1.
Abordagem completa
Lemos e , e mantemos um vetor de três posições chamado top para armazenar os três maiores valores lidos até o momento em ordem decrescente. Para cada cabo lido, atualizamos essa estrutura comparando o novo valor com os maiores atuais de forma eficiente. Após processar todos os cabos em um único loop, testamos sequencialmente as condições: primeiro verificamos se o maior cabo (top[0]) é maior ou igual a , se não for, testamos se a soma de top[0] e top[1] menos 10 atinge , por fim, testamos se a soma dos três maiores (top[0] + top[1] + top[2]) menos 20 é suficiente. Se nenhuma condição for atendida, imprimimos -1. A complexidade de tempo é linear .