Solução Pão a Metro

0 Flares Facebook 0 0 Flares ×

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:

0 Flares Facebook 0 0 Flares ×
0 Flares Facebook 0 0 Flares ×
%d bloggers like this: