18543. Vende-se

Olá meus amigos nerds. Esse mês demorei um pouco a dar as caras por aqui, mas foi por uma boa causa, estava escrevendo um paper :P algo que eu não fazia há muito tempo. E não seria um paper se eu não tivesse que ficar escrevendo e reescrevendo tudo até de madrugada. Vocês não acham? kkk.

Hoje ajudar vamos ajudar nossos amigos da obi a vender algumas casas. Já que é isso que o problema 18543. Vende-se nos pede para fazer. Mais especificamente, (por culpa da Dilma) a obi precisa vender alguns de seus imóveis e quer que os que restarem estejam  o mais próximos possível, ou seja, que a distância entre o primeiro e o último prédios restantes deve ser a menor possível.

Solução

Devo dizer que esse é um problema fácil e quase não tive vontade de escrever sobre ele. Mas esse foi o único problema que eu resolvi essa semana. Então vai ter que servir.

Devemos perceber que as casas restantes serão necessariamente consecutivas (pensando na distância para o início da rua). É só você pensar que para vender uma casa no 'meio' das que restaram, uma casa fora da sequência não poderia ser vendida, mas a distância dessa casa para a casa do canto oposto das que sobraram aumentaria.

Assim basta ordenar as casas pela distância. E percorrer a lista de casas computando a distância pedida.

Implementação

Me desculpem pelo código feio, mas é que eu o fiz enquanto assistia uma palestra chata sobre devops :P