Olá meus amigos nerds. Hoje vamos brincar de cortar pães para fazermos sanduíches que serão usados durante uma maratona de programação. Isso mesmo! Já que é isso que o problema 12939. Pão a metro nos pede para fazer. Mais especificamente, dados os tamanhos de pão disponíveis (em centímetros) e a quantidade de pessoas a serem servidas, queremos saber o tamanho inteiro máximo (em centímetros) da fatia que pode ser cortada de maneira a atender todas as pessoas.
Solução
A solução simples para esse problema seria tentar todos os tamanhos possíveis para os pães e escolher o maior. Entretanto, isso, é claro, não é eficiente o suficiente.
Suponha que conheçamos o tamanho de pão máximo. Para tamanhos superiores de pão não conseguimos servir as n pessoas (caso contrário por contradição esse tamanho não seria máximo). Assim, ao invés de procurar por força bruta o tamanho ótimo, podemos aplicar busca binária ao problema, uma vez que temos uma propriedade que é verificada para valores inferiores a um número (o tamanho máximo), mas não o é para valores inferiores.
Agora só nos falta definir os limites nos quais queremos aplicar busca binária. Obviamente, o tamanho mínimo de pão é 1. Já o máximo é o maior tamanho entre as k fatias de pão (lembre-se de que não podemos juntar duas fatias).
Implementação
Observe que o código testa duas condições de contorno. Uma delas é o pão de tamanho 1 (limite inferior do intervalo) e outra o pão de tamanho k (todos os pedaços são do mesmo tamanho).
Libera a resolução, por favor.
ResponderExcluirA solução está no source code da página. O botão que mostrava ele parou de funcionar kkk. Vou arrumar isso depois, mas enquanto isso você pode converir a solução aqui
Excluir#include
#include
using namespace std;
int valores[10000];
int conta(int k, int m)
{
int p = 0;
for (int i = 0; i < k; i++) {
p += valores[i]/m;
}
return p;
}
bool verifica(int k, int m, int n)
{
return conta(k, m) >= n;
}
int main()
{
int n, k, s;
int low = 1, high = 0, m, p = 0, p1 = 0;
scanf("%d %d", &n, &k);
for (int i = 0; i < k; i++) {
scanf("%d", &valores[i]);
if (high < valores[i]) high = valores[i];
}
for (int i = 0; i < k; i++) {
p += valores[i];
p1 += valores[i]/high;
}
if (p == n) printf("1\n");
else if (p1 == n) printf("%d\n", k);
else {
s = 0;
while (low <= high) {
m = low + (high - low)/2;
p = conta(k, m);
if (verifica(k, m, n)) {
low = m + 1;
s = m;
}
else {
high = m - 1;
}
}
printf("%d\n", s);
}
return 0;
}