Pesquisa Binária - Parte 3: Problema EKO - SPOJ

O último post foi dedicado a alguns fundamentos sobre a pesquisa binária. Às vezes não é óbvio que podemos utilizar este método de pesquisa e obter um algoritmo eficiente. Considerem o problema EKO do SPOJ como exemplo:

Temos uma floresta com 1 000 000 de árvores e queremos obter pelo menos M (<= 2 000 000 000) de madeira. Podemos cortar todas as árvores a uma certa altura inteira, ficando com o que for cortado. A que altura devemos cortar as árvores de modo a obter pelo menos M de madeira e o mínimo desperdício?

No segundo exemplo do enunciado, temos 5 árvores com alturas 5, 26, 40, 42 e 46, e queremos 20 de madeira.

Se cortarmos à altura 30, obtemos 0 + 0 + 10 + 12 + 16 = 38, excessivo.

Se cortarmos à altura 40, obtemos 0 + 0 + 0 + 2 + 6 = 8, insuficiente.

Mas à altura 36 obtemos 0 + 0 + 4 + 6 + 10 = 20 de madeira - perfeito visto que não há desperdício.

Se virmos bem, a quantidade de madeira que obtemos em função da altura a que cortamos as árvores é decrescente. Como se pode ver na figura seguinte, quanto menor for a altura de corte, maior é a quantidade de madeira obtida.

Exemplo com alturas das árvores e linhas de corte

Assim, podemos fazer uma pesquisa binária na altura a cortar. O enunciado garante que existe madeira suficiente, por isso, a altura mínima é 0, enquanto que a altura máxima está limitada pela árvore mais alta. Só precisamos de testar Log(AlturaMáxima) alturas diferentes na pesquisa binária. Para cada altura a testar, podemos percorrer todas as árvores para determinar a quantidade de madeira obtida. 

Logo, o tempo de execução do algoritmo é O(N log AlturaMáxima). Implementação em C++:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

size_t DeterminaAltura(size_t* alturas, size_t n, size_t alvo) { size_t esq = 1, dir = 1000000000, resultado = 0; while (esq <= dir) { // importante usar unsigned int porque soma pode ser >= 2^31 size_t i, mid = (esq+dir) / 2, soma = 0; for (i = 0 ; i < n && soma < alvo ; i++) if (alturas[i] > mid) soma += alturas[i]-mid; if ( soma >= alvo ) { resultado = mid; esq = mid+1; } else { dir = mid-1; } } return resultado; }

Há outras formas de resolver o problema, mas esta pesquisa binária é provavelmente a mais simples e directa.