Koko Eating Bananas

Q: Qual é a complexidade de tempo de Koko Eating Bananas?

A busca binária é executada em tempo O(n log m) , em que n é o número de pilhas e m é a maior pilha. Cada verificação lê todas as pilhas uma vez, e o intervalo de velocidades cai pela metade após cada verificação, então há cerca de log2(m) verificações: 30 quando m = 10^9 . O espaço extra é O(1) .

Q: Por que a busca binária funciona para encontrar a velocidade de ingestão?

A busca binária precisa de uma pergunta de sim ou não cujas respostas estejam ordenadas. “Koko consegue terminar na velocidade k?” é uma delas: uma velocidade maior nunca exige mais horas, porque o valor de p / k arredondado para cima de cada pilha só pode diminuir à medida que k aumenta. Portanto, todas as velocidades abaixo da resposta falham e todas as velocidades a partir da resposta são suficientes, e a busca encontra o limite.

Q: Quais são os limites inferior e superior para a velocidade?

O limite superior é a maior pilha: nessa velocidade, cada pilha leva exatamente uma hora, e h é pelo menos igual ao número de pilhas, então sempre dá tempo. Uma velocidade maior ainda exige uma hora por pilha, portanto buscar acima desse limite não traz nenhum benefício. O limite inferior é 1, e você pode aumentá-lo para o total de bananas dividido por h , arredondado para cima, porque Koko come no máximo k bananas por hora.

Q: Como dividir e arredondar para cima com números inteiros?

Use (p + k-1) / k com divisão inteira. Somar k-1 faz com que qualquer resto passe para o próximo múltiplo de k , enquanto um múltiplo exato permanece onde está: 10 na velocidade 4 resulta em 13 / 4 = 3 , e 8 na velocidade 4 resulta em 11 / 4 = 2 . Isso evita ponto flutuante, em que valores grandes podem ser arredondados incorretamente.

MédioBusca binária

+10

Koko tem n pilhas de bananas, em que piles[i] é o número de bananas na pilha i, e faltam h horas para os guardas voltarem. Ela escolhe uma velocidade de consumo k, um número inteiro de bananas por hora, e a mantém. A cada hora, ela come k bananas de uma pilha; se restarem menos de k bananas nessa pilha, ela a termina e descansa até o fim da hora. Retorne a menor velocidade k que permita que ela termine todas as pilhas em até h horas.

Função

minEatingSpeed(piles: integer-array, h: integer) → integer

pilesinteger-array: o número de bananas em cada pilha
hinteger: o número de horas que Koko tem
Retornainteger: a menor velocidade inteira de consumo, em bananas por hora, que termina todas as pilhas em até h horas

Restrições

1 ≤ piles.length ≤ 5000
1 ≤ piles[i] ≤ 10⁹
piles.length ≤ h ≤ 10⁹, então sempre existe uma resposta.

Exemplos

Entrada: piles = [4, 10, 7, 3]h = 6
Saída: 5
Explicação: Na velocidade 5, as pilhas 4, 10, 7 e 3 levam 1, 2, 2 e 1 horas: 6 no total, o que cabe. Na velocidade 4, elas levam 1, 3, 2 e 1 horas, totalizando 7, uma hora a mais.

+22 testes ocultos ao enviar

Para ir além

Um problema semelhante: Koko tem d dias e come pilhas inteiras na ordem dada, tantas pilhas por dia quantas couberem no limite diário de k bananas. Qual é o menor k, e quais duas partes da sua busca binária mudam?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

A resposta aqui é uma velocidade, não uma posição no array, e isso oculta a busca binária. Verificar uma velocidade exige uma única passagem pelas pilhas. As verificações também seguem uma ordem: se a velocidade k termina a tempo, todas as velocidades maiores também terminam. Assim, você pode fazer uma busca binária entre as velocidades de 1 até a maior pilha e precisa de cerca de 30 verificações, enquanto testar as velocidades uma a uma pode exigir um bilhão.

Tente cada velocidade a partir de 1

Correta, mas não termina nos maiores testes

Intuição

Comece com uma pergunta: quanto tempo leva para comer uma pilha de p bananas à velocidade k? Koko come k bananas por hora e nunca passa para outra pilha durante a mesma hora, então a pilha leva p / k horas, arredondadas para cima. Uma pilha de 10 bananas à velocidade 4 leva 3 horas: 4, 4, depois 2 e uma pausa. Some isso para todas as pilhas e compare o total com h.

Agora teste as velocidades em ordem: 1, 2, 3 e assim por diante, e retorne a primeira cujo total caiba em h. Ela é a menor por construção, já que todas as velocidades menores foram testadas e não deram certo. O loop sempre termina: na velocidade da maior pilha, cada pilha leva uma hora, e h é pelo menos igual ao número de pilhas.

O problema é até onde o loop pode ir. Com 5000 pilhas de quase 10^9 bananas e h = 5000, a resposta fica perto de 10^9, então o loop executa cerca de um bilhão de vezes e cada verificação percorre as 5000 pilhas: cerca de 5 × 10^12 etapas. Aqui, m é a maior pilha.

Algoritmo

Defina speed = 1.
Conte as horas nessa velocidade: para cada pilha, some (pile + speed-1) / speed, usando um total de 64 bits.
Se o total for no máximo h, retorne speed.
Caso contrário, adicione 1 a speed e conte novamente.

def minEatingSpeed(piles, h):
    speed = 1
    while True:
        hours = 0
        for pile in piles:
            hours += (pile + speed - 1) // speed  # a started pile costs a whole hour
        if hours <= h:
            return speed
        speed += 1

Busca binária na velocidade

Intuição

Pense em cada velocidade de 1 até a maior pilha como uma linha de respostas à pergunta “essa velocidade termina a tempo?”. À medida que a velocidade aumenta, cada pilha leva o mesmo número de horas ou menos, então o total só pode diminuir. Portanto, a linha apresenta não, não, não e depois sim a partir da resposta, sem voltar atrás. Você está procurando o primeiro sim, e uma linha ordenada de não e sim é exatamente o que a busca binária divide ao meio.

Mantenha um intervalo de lo a hi que sempre contenha a resposta. Ele começa em 1 e na maior pilha, o que é seguro porque a velocidade igual à maior pilha leva uma hora por pilha, e h é suficiente para isso. Verifique a velocidade do meio, mid. Se ela for suficiente, a resposta é mid ou uma velocidade menor, então defina hi = mid e mantenha mid no intervalo. Se não for suficiente, todas as velocidades menores também falham, então defina lo = mid + 1. Quando lo alcançar hi, essa velocidade será a resposta.

Acompanhe o primeiro exemplo: pilhas 4, 10, 7, 3 com h = 6. O intervalo vai de 1 a 10. A velocidade 5 leva 1 + 2 + 2 + 1 = 6 horas, o que é suficiente, então o intervalo passa a ser de 1 a 5. A velocidade 3 leva 2 + 4 + 3 + 1 = 10 horas, mais do que o permitido, então o intervalo passa a ser de 4 a 5. A velocidade 4 leva 1 + 3 + 2 + 1 = 7 horas, ainda mais do que o permitido, então o intervalo passa a ser de 5 a 5, e a resposta é 5.

Cada verificação reduz o intervalo pela metade, então um intervalo de até 10^9 velocidades precisa de cerca de 30 verificações. Com 5000 pilhas por verificação, isso dá cerca de 150000 etapas, em vez de trilhões.

Algoritmo

Defina lo = 1 e hi como a maior pilha.
Enquanto lo < hi, calcule mid = lo + (hi - lo) / 2.
Conte as horas na velocidade mid: some (pile + mid-1) / mid para cada pilha, usando um total de 64 bits.
Se o total for no máximo h, defina hi = mid; caso contrário, defina lo = mid + 1.
Quando o loop terminar, retorne lo.

def minEatingSpeed(piles, h):
    lo, hi = 1, max(piles)  # the largest pile always works: one hour per pile
    while lo < hi:
        mid = lo + (hi - lo) // 2
        hours = 0
        for pile in piles:
            hours += (pile + mid - 1) // mid
        if hours <= h:
            hi = mid  # mid works, so the answer is mid or slower
        else:
            lo = mid + 1  # mid is too slow, so the answer is faster
    return lo

Armadilhas e casos extremos

A busca em si é curta. Os bugs ficam escondidos na contagem de horas e nos limites do intervalo.

Estourar a contagem de horas. Na velocidade 1, 5000 pilhas de 10^9 bananas levam 5 × 10^12 horas, muito além do limite de 32 bits, que é cerca de 2.1 × 10^9. Um total que sofreu overflow pode ficar pequeno e fazer com que uma velocidade lenta demais passe na verificação. Conte usando um inteiro de 64 bits ou pare de contar assim que o total passar de h.
Arredondar na direção errada. A divisão inteira arredonda para baixo, então 10 / 4 resulta em 2, mas essa pilha leva 3 horas. Arredonde para cima usando (pile + k-1) / k.
Começar o intervalo em 0. Assim, mid pode ser 0 e a contagem de horas divide por zero. A menor velocidade real é 1.
Definir hi como mid - 1 quando mid funciona. Isso pode descartar a própria resposta. Ao buscar a primeira velocidade que funciona, mantenha mid com hi = mid e faça o loop enquanto lo < hi.
Começar com hi abaixo da maior pilha. Velocidades menores que ela podem falhar quando h é igual ao número de pilhas, então a busca retornaria uma velocidade que não funciona.

Perguntas frequentes4

Qual é a complexidade de tempo de Koko Eating Bananas?

A busca binária é executada em tempo O(n log m), em que n é o número de pilhas e m é a maior pilha. Cada verificação lê todas as pilhas uma vez, e o intervalo de velocidades cai pela metade após cada verificação, então há cerca de log2(m) verificações: 30 quando m = 10^9. O espaço extra é O(1).

Por que a busca binária funciona para encontrar a velocidade de ingestão?

A busca binária precisa de uma pergunta de sim ou não cujas respostas estejam ordenadas. “Koko consegue terminar na velocidade k?” é uma delas: uma velocidade maior nunca exige mais horas, porque o valor de p / k arredondado para cima de cada pilha só pode diminuir à medida que k aumenta. Portanto, todas as velocidades abaixo da resposta falham e todas as velocidades a partir da resposta são suficientes, e a busca encontra o limite.

Quais são os limites inferior e superior para a velocidade?

O limite superior é a maior pilha: nessa velocidade, cada pilha leva exatamente uma hora, e h é pelo menos igual ao número de pilhas, então sempre dá tempo. Uma velocidade maior ainda exige uma hora por pilha, portanto buscar acima desse limite não traz nenhum benefício. O limite inferior é 1, e você pode aumentá-lo para o total de bananas dividido por h, arredondado para cima, porque Koko come no máximo k bananas por hora.

Como dividir e arredondar para cima com números inteiros?

Use (p + k-1) / k com divisão inteira. Somar k-1 faz com que qualquer resto passe para o próximo múltiplo de k, enquanto um múltiplo exato permanece onde está: 10 na velocidade 4 resulta em 13 / 4 = 3, e 8 na velocidade 4 resulta em 11 / 4 = 2. Isso evita ponto flutuante, em que valores grandes podem ser arredondados incorretamente.

Python

def minEatingSpeed(piles, h):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

piles = [4, 10, 7, 3]
h = 6

Esperado