Pão a Metro

pao.cpp

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