Solução de Roger Benet, comentários de Rogério Júnior
Este problema caiu na 2ª fase da P1 da OBI 2007. Ele é uma simples busca binária. Nele, vamos usar a ideia da busca binária para chutarmos a resposta de maneira eficiente até encontrarmos a resposta.
Neste problema, imagine um vetor de $$bool$$, onde a posição $$i$$ é $$false$$ se eu não consigo dividir os pães com tamanho $$i$$, e $$true$$ caso eu consiga. A partir de certo tamanho, não consigo mais dividir, logo o vetor se tornaria vários $$true$$ consecutivos seguidos de vários $$false$$. Usaremos a busca binária para encontrar a última posição que ainda é $$true$$.
Nesse caso, é simples checar se a posição $$i$$ do vetor é $$true$$, basta, em $$O(N)$$, percorrermos todos os pães, vermos em quantas fatias podemos dividi-lo e verificar se esse número é o suficiente para o número de pessoas. Como a busca binária tem complexidade $$O(log \ N)$$, essa operação só será feita $$O(log \ N)$$ vezes, o que gera uma complexidade de $$O(N \ log \ N)$$.
Se você não conhece a ideia da busca binária, clique aqui para ver a aula do Curso Noic.
Segue o código para melhor entendimento:
https://gist.github.com/rogerioagjr/7d17c2102e2a86ab833f
Deixe um comentário