Solução Pão a Metro

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:


#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;
}

view raw

pao.cpp

hosted with ❤ by GitHub