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: cerca de log2(m) verificações, 30 quando m = 10^9 , cada uma lendo todas as pilhas uma vez. O espaço extra é O(1) .

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

O limite superior é a maior pilha: nesse caso, cada pilha leva uma hora, o que sempre cabe no tempo disponível. O limite inferior é 1, e você pode aumentá-lo para o número 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 ultrapasse o próximo múltiplo de k , enquanto um múltiplo exato permanece igual: 10 na velocidade 4 resulta em 13 / 4 = 3 , e 8 resulta em 11 / 4 = 2 . Não é necessário usar ponto flutuante.

MédioBusca binária

+10

Koko tem n pilhas de bananas, com piles[i] bananas na pilha i, e h horas. 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 o menor 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 para comer, em bananas por hora, que consome todas as pilhas dentro de h horas

Restrições

1 ≤ piles.length ≤ 5000
1 ≤ piles[i] ≤ 10⁹
piles.length ≤ h ≤ 10⁹, portanto 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, totalizando 7.

Para ir além

Problema gêmeo: Koko come pilhas inteiras em ordem, no máximo k bananas por dia, dentro de d dias. Qual é o menor k, e o que muda na sua busca?

Dicas

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

0 de 3 abertas

Solução

A resposta é uma velocidade, não uma posição no array, e isso esconde uma busca binária. Verificar uma velocidade exige uma passagem pelas pilhas e, se a velocidade k permite terminar a tempo, todas as velocidades maiores também permitem. Então, faça uma busca binária nas velocidades de 1 até a maior pilha: cerca de 30 verificações em vez de até um bilhão.

Experimente cada velocidade a partir de 1

Correta, mas não termina nos maiores testes

Intuição

Koko nunca passa para outra pilha dentro de uma hora, então uma pilha com p bananas leva p / k horas, arredondadas para cima: com velocidade 4, 10 bananas levam 3 horas. Teste velocidades 1, 2, 3 e assim por diante, e retorne a primeira cuja soma caiba em h. Ela é a menor porque todas as velocidades menores falharam, e o loop para na velocidade da maior pilha, quando cada pilha leva uma hora.

Com m sendo a maior pilha, são até m verificações de n pilhas: cerca de 5 × 10^12 etapas para 5000 pilhas próximas de 10^9 e h = 5000.

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

À medida que a velocidade aumenta, cada pilha leva o mesmo número de horas ou menos, então as respostas para “essa velocidade termina a tempo?” são não, não, não e, depois, sim a partir da resposta. A busca binária encontra esse primeiro sim.

Mantenha um intervalo de lo a hi que sempre contém a resposta, começando em 1 e na pilha maior, cuja velocidade leva uma hora por pilha e, portanto, é suficiente. Se a velocidade do meio mid for suficiente, a resposta é mid ou mais lenta, então defina hi = mid. Se não, todas as velocidades mais lentas também falham, então defina lo = mid + 1. Quando lo alcançar hi, essa será a resposta.

No primeiro exemplo, o intervalo começa em 1 a 10. A velocidade 5 é suficiente, então o intervalo passa a ser de 1 a 5; a velocidade 3 leva 10 horas, então o intervalo passa a ser de 4 a 5; a velocidade 4 leva 7 horas, então o intervalo passa a ser de 5 a 5.

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, em um total de 64 bits.
Se o total for no máximo h, defina hi = mid; caso contrário, defina lo = mid + 1.
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

Estourar a contagem de horas. Na velocidade 1, 5000 pilhas de 10^9 bananas levam 5 × 10^12 horas, ultrapassando o limite de 32 bits, e um total que sofreu overflow pode fazer uma velocidade baixa ser aprovada. Conte usando 64 bits ou pare assim que o total ultrapassar h.
Arredondar para baixo. 10 / 4 resulta em 2, mas essa pilha leva 3 horas.
Começar o intervalo em 0. Assim, mid pode ser 0 e a contagem divide por zero.
Definir hi = mid - 1 quando mid funciona. Isso pode descartar a resposta.
Começar com hi abaixo da pilha maior. Quando h é igual ao número de pilhas, todas as velocidades menores falham, e a busca retorna uma delas.

Perguntas frequentes3

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: cerca de log2(m) verificações, 30 quando m = 10^9, cada uma lendo todas as pilhas uma vez. O espaço extra é O(1).

Quais são os limites inferior e superior da velocidade?

O limite superior é a maior pilha: nesse caso, cada pilha leva uma hora, o que sempre cabe no tempo disponível. O limite inferior é 1, e você pode aumentá-lo para o número 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 ultrapasse o próximo múltiplo de k, enquanto um múltiplo exato permanece igual: 10 na velocidade 4 resulta em 13 / 4 = 3, e 8 resulta em 11 / 4 = 2. Não é necessário usar ponto flutuante.

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

Teste #1

Teste #2

Teste #3

Argumentos

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

Saída Esperada