Koko Eating Bananas

Q: Quelle est la complexité temporelle de Koko Eating Bananas ?

La recherche binaire s’exécute en O(n log m) , où n est le nombre de tas et m le plus grand tas : environ log2(m) vérifications, 30 lorsque m = 10^9 , chacune parcourant tous les tas une fois. L’espace supplémentaire est de O(1) .

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

La borne supérieure est le plus grand tas : avec cette valeur, chaque tas prend une heure, ce qui convient toujours. La borne inférieure est 1, et tu peux l’augmenter jusqu’au nombre total de bananes divisé par h , arrondi à l’entier supérieur, car Koko mange au maximum k bananes par heure.

Q: Comment diviser et arrondir à l’entier supérieur avec des entiers ?

Utilisez (p + k-1) / k avec une division entière. Ajouter k-1 pousse tout reste au-delà du multiple suivant de k , tandis qu’un multiple exact reste inchangé : 10 à la vitesse 4 donne 13 / 4 = 3 , et 8 donne 11 / 4 = 2 . Aucun nombre à virgule flottante n’est nécessaire.

MoyenRecherche binaire

+10

Koko a n tas de bananes, avec piles[i] bananes dans le tas i, et h heures. 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 plus petite valeur de k qui lui permet de finir tous les tas en h heures.

Fonction

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

pilesinteger-array: le nombre de bananes dans chaque tas
hinteger: le nombre d’heures dont dispose Koko
Renvoieinteger: la plus petite vitesse entière de consommation, en bananes par heure, qui permet de finir 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 1, 2, 2 et 1 heures : 6 au total, ce qui convient. À la vitesse 4, elles prennent 1, 3, 2 et 1, soit 7.

Pour aller plus loin

Problème des bananes : Koko mange des piles entières dans l’ordre, au plus k bananes par jour, en d jours. Quelle est la plus petite valeur de k, et que changez-vous dans votre recherche ?

Indices

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

0 sur 3 ouverts

Solution

La réponse est une vitesse, pas une position dans le tableau, ce qui cache une recherche binaire. Vérifier une vitesse nécessite un seul passage sur les tas, et si la vitesse k permet de terminer à temps, toutes les vitesses supérieures le permettent aussi. Il suffit donc d’effectuer une recherche binaire parmi les vitesses allant de 1 à la pile la plus grande : environ 30 vérifications au lieu d’un milliard au maximum.

Essayez toutes les vitesses à partir de 1.

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Koko ne passe jamais à une autre pile avant qu'une heure se soit écoulée, donc une pile de p bananes prend p / k heures, arrondi à l'entier supérieur : à la vitesse 4, 10 bananes prennent 3 heures. Essaie les vitesses 1, 2, 3, et ainsi de suite, puis renvoie la première dont le temps total ne dépasse pas h. C'est la plus petite, car toutes les vitesses plus lentes ont échoué, et la boucle s'arrête à la vitesse de la plus grande pile, à laquelle chaque pile prend une heure.

Avec m comme taille de la plus grande pile, cela représente jusqu'à m vérifications de n piles : environ 5 × 10^12 étapes pour 5000 piles proches de 10^9 et h = 5000.

Algorithme

Définis speed = 1.
Compte les heures à cette vitesse : pour chaque tas, ajoute (pile + speed-1) / speed, en utilisant un total sur 64 bits.
Si le total est inférieur ou égal à h, retourne speed.
Sinon, ajoute 1 à speed et compte à 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 sur la vitesse

Intuition

À mesure que la vitesse augmente, chaque tas nécessite le même nombre d’heures ou moins ; les réponses à « cette vitesse permet-elle de finir à temps ? » sont donc non, non, non, puis oui à partir de la réponse. La recherche binaire trouve ce premier oui.

Conserve un intervalle de lo à hi qui contient toujours la réponse, en commençant à 1 et en prenant le plus grand tas, dont la vitesse nécessite une heure par tas et convient donc. Si la vitesse médiane mid convient, la réponse est mid ou une vitesse inférieure ; définis donc hi = mid. Sinon, toutes les vitesses inférieures échouent aussi ; définis donc lo = mid + 1. Lorsque lo rejoint hi, c’est la réponse.

Dans le premier exemple, l’intervalle commence de 1 à 10. La vitesse 5 convient, donc l’intervalle devient de 1 à 5 ; à la vitesse 3, il faut 10 heures, donc l’intervalle devient de 4 à 5 ; à la vitesse 4, il faut 7 heures, donc l’intervalle devient de 5 à 5.

Algorithme

Définissez lo = 1 et hi comme étant 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.
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

Débordement du nombre d'heures. À la vitesse 1, 5000 piles de 10^9 bananes nécessitent 5 × 10^12 heures, ce qui dépasse la limite des 32 bits, et un total qui déborde peut laisser passer une vitesse trop lente. Faites le calcul sur 64 bits, ou arrêtez-vous dès que le total dépasse h.
Arrondi à l’inférieur. 10 / 4 donne 2, pourtant cette pile nécessite 3 heures.
Commencer l’intervalle à 0. Alors mid peut être égal à 0 et le calcul du nombre d’heures provoque une division par zéro.
Définir hi = mid - 1 lorsque mid satisfait la condition. Cela peut éliminer la réponse.
Commencer avec hi inférieur à la plus grande pile. Lorsque h est égal au nombre de piles, toutes les vitesses inférieures échouent, et la recherche renvoie l’une d’elles.

Questions fréquentes3

Quelle est la complexité temporelle de Koko Eating Bananas ?

La recherche binaire s’exécute en O(n log m), où n est le nombre de tas et m le plus grand tas : environ log2(m) vérifications, 30 lorsque m = 10^9, chacune parcourant tous les tas une fois. L’espace supplémentaire est de O(1).

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

La borne supérieure est le plus grand tas : avec cette valeur, chaque tas prend une heure, ce qui convient toujours. La borne inférieure est 1, et tu peux l’augmenter jusqu’au nombre total de bananes divisé par h, arrondi à l’entier supérieur, car Koko mange au maximum k bananes par heure.

Comment diviser et arrondir à l’entier supérieur avec des entiers ?

Utilisez (p + k-1) / k avec une division entière. Ajouter k-1 pousse tout reste au-delà du multiple suivant de k, tandis qu’un multiple exact reste inchangé : 10 à la vitesse 4 donne 13 / 4 = 3, et 8 donne 11 / 4 = 2. Aucun nombre à virgule flottante n’est nécessaire.

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

Test #1

Test #2

Test #3

Arguments

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

Résultat attendu