2609. Trilhas

Olá meus amigos nerds. Hoje vamos brincar fazer trilhas, já que é isso que o problema 2609. Trilhas nos pede para fazer. Mais especificamente, dadas as informações sobre distâncias e altitudes de um conjunto de trilhas, determinar qual é a trilha que exige o menor esforço de subida. Onde o esforço de subida é proporcional ao desnível do trecho percorrido.

Solução

O problema não nos diz como calcular o esforço de subida, mas apenas que ele é proporcional ao desnível do trecho, em outras palavras à altura do trecho subido. Ora mas se o esforço é proporcional a cada uma das alturas ele será proporcional a soma delas. Sendo assim, o problema fica bem fácil, basta calcular a soma das alturas. Para isso, é só percorrer o vetor com a altura dos trechos e ir fazendo as diferenças entre dois trechos seguidos.

Um detalhe importante é que ele não se importa com o sentido do trecho, assim sendo devemos calcular o desnível do terreno considerando que ele pode estar indo do trecho a para o b, ou vice versa.

A resposta final será a opção de trilha com a menor soma das alturas.

Implementação