Olá meus amigos nerds. Hoje vamos calcular a área aberta de uma janela. Já que é isso que o problema 18553. Janela nos pede para fazer. Mais especificamente, dadas as posições de vários pedaços de vidro e seus comprimentos e o comprimento total da janela determinar qual a área total da janela que está aberta.
Solução
Devo confessar, quando comecei a ler esse problema pensei que ele seria um pouco mais difícil, mas o tamanho da entrada (3) é tão pequeno que por força bruta é possível faze-lo. Vou ignorar esse fato e mostrar como seria possível resolver esse problema, caso os vidros da janela fossem de tamanhos diferentes e em maior número.
O problema consiste em encontrar pedaços da janela que não estejam cobertos por nenhum vidro. Qual é a condição necessária e suficiente para que um pedaço da janela não esteja coberto? Se pensarmos bem, essa condição é até bem simples (depois que a vemos, é claro!). Um buraco é definido por um fim de janela e pelo inicio da primeira janela seguinte, ou seja, só pode haver um buraco se o ponto de inicio de uma janela for maior que o ponto de termino da janela anterior.
Mas como garantir que não existiram outros pedaços de vidro entre esses pontos? Isso é fácil, basta ordenar os pedaços de janela pelo ponto em que elas terminam. Pense nos pedaços i e i+1 ordenados. Não pode haver uma janela que termine em um ponto entre o fim de i e de i+1, caso contrário i e i+1 não poderiam seguir um ao outro na ordenação, deveriam ter o ponto de fim desse terceiro pedaço entre eles.
Sendo assim, a solução do problema consiste em ordenar os pedaços de vidro pelo seu ponto de fim e ir somando os espaços entre o inicio da próxima janela e o fim da anterior.
O problema consiste em encontrar pedaços da janela que não estejam cobertos por nenhum vidro. Qual é a condição necessária e suficiente para que um pedaço da janela não esteja coberto? Se pensarmos bem, essa condição é até bem simples (depois que a vemos, é claro!). Um buraco é definido por um fim de janela e pelo inicio da primeira janela seguinte, ou seja, só pode haver um buraco se o ponto de inicio de uma janela for maior que o ponto de termino da janela anterior.
Mas como garantir que não existiram outros pedaços de vidro entre esses pontos? Isso é fácil, basta ordenar os pedaços de janela pelo ponto em que elas terminam. Pense nos pedaços i e i+1 ordenados. Não pode haver uma janela que termine em um ponto entre o fim de i e de i+1, caso contrário i e i+1 não poderiam seguir um ao outro na ordenação, deveriam ter o ponto de fim desse terceiro pedaço entre eles.
Sendo assim, a solução do problema consiste em ordenar os pedaços de vidro pelo seu ponto de fim e ir somando os espaços entre o inicio da próxima janela e o fim da anterior.
Nenhum comentário:
Postar um comentário