Koko Eating Bananas

Q: Quelle est la complexité temporelle de Koko mange des bananes ?

La recherche binaire s’exécute en temps O(n log m) , où n est le nombre de piles et m la plus grande pile. Chaque vérification parcourt chaque pile une fois, et l’intervalle des vitesses est divisé par deux après chaque vérification, donc il y a environ log2(m) vérifications : 30 lorsque m = 10^9 . L’espace supplémentaire est de O(1) .

Q: Pourquoi la recherche binaire fonctionne-t-elle pour la vitesse à laquelle on mange ?

La recherche binaire nécessite une question à laquelle on répond par oui ou non et dont les réponses sont triées. « Koko peut-elle terminer à la vitesse k ? » en est une : une vitesse plus élevée ne nécessite jamais plus d’heures, car le résultat de p / k arrondi à l’entier supérieur pour chaque tas ne peut que diminuer à mesure que k augmente. Ainsi, toute vitesse inférieure à la réponse échoue et toute vitesse à partir de la réponse réussit ; la recherche trouve donc la frontière.

Q: Quelles sont les bornes inférieure et supérieure de la vitesse ?

La borne supérieure est la pile la plus grande : à cette vitesse, chaque pile prend exactement une heure, et h est supérieur ou égal au nombre de piles, donc cela fonctionne toujours. Une vitesse plus élevée nécessite toujours une heure par pile, donc chercher au-delà ne sert à rien. La borne inférieure est 1, et vous pouvez la resserrer en prenant le nombre total de bananes divisé par h , arrondi à l’entier supérieur, car Koko mange au maximum k bananes par heure.

Q: Comment diviser des entiers et arrondir le résultat au supérieur ?

Utilisez (p + k-1) / k avec une division entière. Ajouter k-1 fait passer tout reste au multiple suivant de k , tandis qu’un multiple exact reste inchangé : 10 à la vitesse 4 donne 13 / 4 = 3 , et 8 à la vitesse 4 donne 11 / 4 = 2 . Cela évite les nombres à virgule flottante, avec lesquels les grandes valeurs peuvent être arrondies dans le mauvais sens.

MoyenRecherche binaire

+10

Koko a n tas de bananes, où piles[i] est le nombre de bananes dans le tas i, et il lui reste h heures avant le retour des gardes. Elle choisit une vitesse de consommation k, un nombre entier de bananes par heure, et la conserve. Chaque heure, elle mange k bananes dans un tas ; s’il en reste moins de k dans ce tas, elle le termine et se repose jusqu’à la fin de l’heure. Retournez la vitesse minimale k qui lui permet de terminer tous les tas en h heures.

Fonction

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

pilesinteger-array: le nombre de bananes dans chaque pile
hinteger: le nombre d’heures dont dispose Koko
Renvoieinteger: la plus petite vitesse entière de consommation, en bananes par heure, qui permet de terminer chaque tas en h heures

Contraintes

1 ≤ piles.length ≤ 5000
1 ≤ piles[i] ≤ 10⁹
piles.length ≤ h ≤ 10⁹, donc une réponse existe toujours.

Exemples

Entrée: piles = [4, 10, 7, 3]h = 6
Sortie: 5
Explication: À la vitesse 5, les piles 4, 10, 7 et 3 prennent respectivement 1, 2, 2 et 1 heures : 6 au total, ce qui convient. À la vitesse 4, elles prennent respectivement 1, 3, 2 et 1 heures, soit 7, une heure de trop.

+22 tests cachés à la soumission

Pour aller plus loin

Un problème similaire : Koko a d jours et mange des tas entiers dans l’ordre donné, autant de tas par jour que le permet une limite quotidienne de k bananes. Quelle est la plus petite valeur de k, et quelles sont les deux parties de ta recherche binaire qui changent ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

La réponse ici est une vitesse, et non une position dans le tableau, ce qui masque la recherche binaire. Vérifier une vitesse nécessite un seul passage sur les tas. Les vérifications s’enchaînent aussi dans l’ordre : si la vitesse k permet de terminer à temps, toutes les vitesses supérieures le permettent aussi. On peut donc effectuer une recherche binaire parmi les vitesses allant de 1 à la taille du plus grand tas, ce qui nécessite environ 30 vérifications, alors qu’essayer les vitesses une par une peut en nécessiter un milliard.

Essaie chaque vitesse à partir de 1

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Commencez par une question : combien de temps faut-il à un tas de p bananes à la vitesse k ? Koko mange k bananes par heure et ne passe jamais à un autre tas au cours de la même heure, donc il lui faut p / k heures, arrondies à l’entier supérieur, pour finir le tas. Un tas de 10 bananes à la vitesse 4 prend 3 heures : 4, 4, puis 2 et une pause. Additionnez le tout pour tous les tas et comparez le total à h.

Essayez maintenant les vitesses dans l’ordre : 1, 2, 3, et ainsi de suite, puis renvoyez la première dont le total ne dépasse pas h. C’est la plus petite par construction, puisque toutes les vitesses plus lentes ont été essayées et ont échoué. La boucle s’arrête toujours : à la vitesse du plus grand tas, chaque tas prend une heure, et h est supérieur ou égal au nombre de tas.

Le problème, c’est la durée possible de la boucle. Avec 5000 tas de presque 10^9 bananes et h = 5000, la réponse est proche de 10^9, donc la boucle s’exécute environ un milliard de fois et chaque vérification parcourt les 5000 tas : environ 5 × 10^12 étapes. Ici, m est le plus grand tas.

Algorithme

Définissez speed = 1.
Comptez les heures à cette vitesse : pour chaque tas, ajoutez (pile + speed-1) / speed, en utilisant un total sur 64 bits.
Si le total est inférieur ou égal à h, renvoyez speed.
Sinon, ajoutez 1 à speed et comptez à nouveau.

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

Recherche binaire de la vitesse

Intuition

Imagine que chaque vitesse de 1 jusqu’au plus grand tas corresponde à une ligne de réponses à la question « cette vitesse permet-elle de terminer à temps ? ». À mesure que la vitesse augmente, chaque tas prend le même nombre d’heures ou moins, donc le total ne peut que diminuer. La ligne contient donc des « non », puis des « oui » à partir de la réponse, sans jamais revenir en arrière. Tu cherches le premier « oui », et une ligne triée de « non » et de « oui », c’est exactement ce que la recherche binaire divise en deux.

Garde un intervalle lo à hi qui contient toujours la réponse. Il commence à 1 et au plus grand tas, ce qui est sûr, car la vitesse correspondant au plus grand tas prend une heure par tas et h suffit pour cela. Vérifie la vitesse médiane mid. Si elle convient, la réponse est mid ou une vitesse inférieure, alors définis hi = mid et garde mid dans l’intervalle. Si elle ne convient pas, toutes les vitesses inférieures échouent aussi, alors définis lo = mid + 1. Quand lo rejoint hi, cette vitesse est la réponse.

Suivons le premier exemple : les tas 4, 10, 7, 3 avec h = 6. L’intervalle va de 1 à 10. À la vitesse 5, il faut 1 + 2 + 2 + 1 = 6 heures, ce qui convient, alors l’intervalle devient 1 à 5. À la vitesse 3, il faut 2 + 4 + 3 + 1 = 10 heures, ce qui est trop, alors l’intervalle devient 4 à 5. À la vitesse 4, il faut 1 + 3 + 2 + 1 = 7 heures, toujours trop, alors l’intervalle devient 5 à 5, et la réponse est 5.

Chaque vérification divise l’intervalle par deux, donc un intervalle contenant jusqu’à 10^9 vitesses nécessite environ 30 vérifications. À 5000 tas par vérification, cela représente environ 150000 étapes au lieu de billions.

Algorithme

Définissez lo = 1 et hi sur la plus grande pile.
Tant que lo < hi, prenez mid = lo + (hi - lo) / 2.
Comptez les heures à la vitesse mid : ajoutez (pile + mid-1) / mid pour chaque pile, dans un total sur 64 bits.
Si le total est inférieur ou égal à h, définissez hi = mid ; sinon, définissez lo = mid + 1.
Lorsque la boucle se termine, renvoyez 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

Pièges et cas limites

La recherche elle-même est courte. Les bugs se cachent dans le décompte des heures et aux limites de l’intervalle.

Débordement du décompte des heures. À la vitesse 1, 5000 tas de 10^9 bananes prennent 5 × 10^12 heures, bien au-delà de la limite des entiers 32 bits, d’environ 2.1 × 10^9. Un total qui déborde peut devenir faible et faire passer la vérification à une vitesse trop lente. Utilise un entier 64 bits, ou arrête le décompte dès que le total dépasse h.
Arrondir dans le mauvais sens. La division entière arrondit vers le bas : 10 / 4 donne donc 2, alors que ce tas nécessite 3 heures. Arrondis vers le haut avec (pile + k-1) / k.
Commencer l’intervalle à 0. Alors, mid peut être égal à 0 et le calcul du nombre d’heures provoque une division par zéro. La vitesse réelle la plus lente est 1.
Déplacer hi à mid - 1 quand mid convient. Tu risques ainsi d’écarter la réponse elle-même. Lorsque tu recherches la première vitesse qui convient, conserve mid en faisant hi = mid et boucle tant que lo < hi.
Commencer avec hi inférieur à la taille du plus grand tas. Les vitesses inférieures peuvent toutes échouer lorsque h est égal au nombre de tas ; la recherche renverrait donc une vitesse qui ne convient pas.

Questions fréquentes4

Quelle est la complexité temporelle de Koko mange des bananes ?

La recherche binaire s’exécute en temps O(n log m), où n est le nombre de piles et m la plus grande pile. Chaque vérification parcourt chaque pile une fois, et l’intervalle des vitesses est divisé par deux après chaque vérification, donc il y a environ log2(m) vérifications : 30 lorsque m = 10^9. L’espace supplémentaire est de O(1).

Pourquoi la recherche binaire fonctionne-t-elle pour la vitesse à laquelle on mange ?

La recherche binaire nécessite une question à laquelle on répond par oui ou non et dont les réponses sont triées. « Koko peut-elle terminer à la vitesse k ? » en est une : une vitesse plus élevée ne nécessite jamais plus d’heures, car le résultat de p / k arrondi à l’entier supérieur pour chaque tas ne peut que diminuer à mesure que k augmente. Ainsi, toute vitesse inférieure à la réponse échoue et toute vitesse à partir de la réponse réussit ; la recherche trouve donc la frontière.

Quelles sont les bornes inférieure et supérieure de la vitesse ?

La borne supérieure est la pile la plus grande : à cette vitesse, chaque pile prend exactement une heure, et h est supérieur ou égal au nombre de piles, donc cela fonctionne toujours. Une vitesse plus élevée nécessite toujours une heure par pile, donc chercher au-delà ne sert à rien. La borne inférieure est 1, et vous pouvez la resserrer en prenant le nombre total de bananes divisé par h, arrondi à l’entier supérieur, car Koko mange au maximum k bananes par heure.

Comment diviser des entiers et arrondir le résultat au supérieur ?

Utilisez (p + k-1) / k avec une division entière. Ajouter k-1 fait passer tout reste au multiple suivant de k, tandis qu’un multiple exact reste inchangé : 10 à la vitesse 4 donne 13 / 4 = 3, et 8 à la vitesse 4 donne 11 / 4 = 2. Cela évite les nombres à virgule flottante, avec lesquels les grandes valeurs peuvent être arrondies dans le mauvais sens.

Python

def minEatingSpeed(piles, h):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

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

Attendu