Limite minimale de balles dans un sac

1760. Limite minimale de balles dans un sac

Difficulté :Moyen

Sujets : Tableau, recherche binaire

Vous recevez un tableau d'entiers nums où le i^ème sac contient des boules nums[i]. Vous recevez également un nombre entier maxOperations.

Vous pouvez effectuer l'opération suivante au maximum des heures maxOperations :

• Prenez n'importe quel sac de balles et divisez-le en deux nouveaux sacs avec un nombre positif de balles.
  • Par exemple, un sac de 5 balles peut devenir deux nouveaux sacs de 1 et 4 balles, ou deux nouveaux sacs de 2 et 3 balles.

Votre pénalité est le nombre maximum de balles dans un sac. Vous souhaitez minimiser votre pénalité après les opérations.

Restituer la pénalité minimale possible après avoir effectué les opérations.

Exemple 1 :

• Entrée : nums = [9], maxOperations = 2
• Sortie : 3
• Explication :
  • Divisez le sac de 9 balles en deux sacs de tailles 6 et 3. [9] -> [6,3].
  • Divisez le sac contenant 6 balles en deux sacs de tailles 3 et 3. [6,3] -> [3,3,3].
  • Le sac avec le plus grand nombre de balles contient 3 balles, votre pénalité est donc de 3 et vous devez en rendre 3.

Exemple 2 :

• Entrée : nums = [2,4,8,2], maxOperations = 4
• Sortie : 2
• Explication :
  • Divisez le sac de 8 balles en deux sacs de tailles 4 et 4. [2,4,8,2] -> [2,4,4,4,2].
  • Divisez le sac contenant 4 balles en deux sacs de tailles 2 et 2. [2,4,4,4,2] -> [2,2,2,4,4,2].
  • Divisez le sac contenant 4 balles en deux sacs de tailles 2 et 2. [2,2,2,4,4,2] -> [2,2,2,2,2,4,2].
  • Divisez le sac contenant 4 balles en deux sacs de tailles 2 et 2. [2,2,2,2,2,4,2] -> [2,2,2,2,2,2,2,2].
  • Le sac avec le plus grand nombre de balles contient 2 balles, votre pénalité est donc de 2 et vous devez en rendre 2.

Contraintes :

• 1 <= nums.length <= 10⁵
• 1 <= maxOperations, nums[i] <= 10⁹

Indice :

1. Changeons la question si nous connaissons la taille maximale d'un sac quel est le nombre minimum de sacs que vous pouvez fabriquer
2. notez qu'à mesure que la taille maximale augmente, le nombre minimum de sacs diminue afin que nous puissions effectuer une recherche binaire de la taille maximale

Solution :

Nous pouvons utiliser la recherche binaire pour trouver la pénalité minimale possible. L’idée clé est que si nous pouvons déterminer si une pénalité donnée est réalisable, nous pouvons affiner la plage de recherche en utilisant la recherche binaire.

Étapes à résoudre :

1. Configuration de la recherche binaire :

   • La pénalité minimale est de 1 (toutes les balles sont divisées en sacs d'une seule balle).
   • La pénalité maximale est le plus grand nombre du tableau nums.

2. Vérification de faisabilité :

   • Pour une pénalité moyenne donnée, vérifiez s'il est possible d'y parvenir avec au maximum les fractionnements maxOperations.
   • Pour ce faire, pour chaque taille de sac en chiffres, calculez le nombre de divisions nécessaires pour que tous les sacs aient des boules moyennes ou moins. Si le nombre total de divisions dépasse maxOperations, la pénalité moyenne n'est pas réalisable.

3. Itérer :

   • Utilisez la recherche binaire pour ajuster la plage [faible, élevée] selon qu'une pénalité moyenne est réalisable.

Implémentons cette solution en PHP : 1760. Limite minimale de balles dans un sac

  
  
  Explication:




Recherche binaire :


L'espace de recherche est compris entre 1 et le nombre maximum dans le tableau nums.
Le point médian représente la pénalité actuelle que nous testons.



Vérification de faisabilité (canAchievePenalty) :


Pour chaque sac, calculez les divisions requises pour vous assurer que tous les sacs ont des boules moyennes ou moins :



ceil(balls / mid) - 1 donne le nombre de fractionnements nécessaires.


Si le total des divisions dépasse maxOperations, la pénalité n'est pas réalisable.



Ajuster l'espace de recherche :


Si la pénalité est réalisable, réduisez la limite supérieure (haut = milieu).
Sinon, augmentez la limite inférieure (bas = milieu 1).



Résultat :


Lorsque la boucle se termine, low contient la plus petite pénalité possible.





  
  
  Complexité:




Complexité temporelle : O(n . log(max(nums)))


La recherche binaire s'exécute dans O(log(max(nums))), et la vérification de faisabilité pour chaque point médian prend O(n).







Complexité spatiale : O(1), car nous n'utilisons que de l'espace supplémentaire constant.



Liens de contact

Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !

Si vous souhaitez du contenu plus utile comme celui-ci, n'hésitez pas à me suivre :


LinkedIn
GitHub



          

            
  

            
        
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!