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 
, onde a posição 
é 
se eu não consigo dividir os pães com tamanho , e 
caso eu consiga. A partir de certo tamanho, não consigo mais dividir, logo o vetor se tornaria vários consecutivos seguidos de vários . Usaremos a busca binária para encontrar a última posição que ainda é .
Nesse caso, é simples checar se a posição do vetor é , basta, em 
, 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 
, essa operação só será feita vezes, o que gera uma complexidade de 
.
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:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <cstdio> | |
| #include <algorithm> | |
| using namespace std; | |
| #define MAXN 10010 | |
| int n, k, p, vet[MAXN]; | |
| // função que testa se posso alimentar todas as pessoas | |
| // com pedaços de pão de tamanho x | |
| bool ok(int x){ | |
| // qtd será o número de pessoas atendidas | |
| int qtd = 0; | |
| // para cada pão | |
| for(int i = 1; i <= k; i++){ | |
| // adiciono a qtd o número de pedaços em que posso dividi-lo | |
| qtd += vet[i]/x; | |
| // e se esse número superar qtd, retorno true | |
| if(qtd >= n) return true; | |
| } | |
| // caso eu percorra todos os pães | |
| //e ainda não tenha atendido odas as pessoas | |
| return false; // retorno false | |
| } | |
| // função que realiza a busca binária | |
| int buscab(int m){ | |
| // i será o início e f o fim | |
| // do intervalo em que realizaremos a busca | |
| // ans será a resposta | |
| int i = 1, f = m, ans = 0; | |
| // enquanto i<=f | |
| while(i <= f){ | |
| // olho para o meio do intervalo | |
| int q = (i+f)/2; | |
| // se posso atender às pessoas com fatias de tamanho q | |
| if(ok(q)){ | |
| //q é uma possível resposta | |
| ans = max(q, ans); | |
| // e as outras estão a sua direita | |
| i = q+1; | |
| } | |
| // se não, a resposta está à esquerda | |
| else f = q-1; | |
| } | |
| // retorno a resposta | |
| return ans; | |
| } | |
| int main(){ | |
| // leio os valores de n e k | |
| scanf("%d %d", &n, &k); | |
| // para cada pão | |
| for(int i = 1; i <= k; i++){ | |
| // salvo seu tamanho em um vetor | |
| scanf("%d", &vet[i]); | |
| // e guardo o maior pedaço que já apareceu | |
| // para saber até onde a busca binária vai | |
| p = max(p, vet[i]); | |
| } | |
| // imprimo o resultado da busca binária | |
| printf("%d\n", buscab(p)); | |
| return 0; | |
| } |