Maximum minimisé de produits distribués dans n'importe quel magasin

2064. Maximum minimisé de produits distribués dans n'importe quel magasin

Difficulté :Moyen

Sujets : Tableau, recherche binaire

Vous recevez un nombre entier n indiquant qu'il existe n magasins de détail spécialisés. Il existe m types de produits de quantités variables, qui sont donnés sous la forme d'un tableau de quantités entières indexées à 0, où quantités[i] représente le nombre de produits du i^ième type de produit.

Vous devez distribuer tous les produits aux magasins de détail en suivant ces règles :

• Un magasin ne peut recevoir qu'au plus un type de produit mais peut en recevoir n'importe quelle quantité.
• Après distribution, chaque magasin aura reçu un certain nombre de produits (éventuellement 0). Soit x représente le nombre maximum de produits offerts à n'importe quel magasin. Vous voulez que x soit aussi petit que possible, c'est-à-dire que vous voulez minimiser le nombre maximal de produits qui sont offerts à n'importe quel magasin.

Renvoyer le minimum x possible.

Exemple 1 :

• Entrée : n = 6, quantités = [11,6]
• Sortie : 3
• Explication : Une méthode optimale est :
  • Les 11 produits de type 0 sont distribués aux quatre premiers magasins dans ces montants : 2, 3, 3, 3
  • Les 6 produits de type 1 sont distribués aux deux autres magasins dans ces montants : 3, 3
  • Le nombre maximum de produits offerts à un magasin est max(2, 3, 3, 3, 3, 3) = 3.

Exemple 2 :

• Entrée : n = 7, quantités = [15,10,10]
• Sortie : 5
• Explication : Une méthode optimale est :
  • Les 15 produits de type 0 sont distribués aux trois premiers magasins dans ces montants : 5, 5, 5
  • Les 10 produits de type 1 sont distribués aux deux magasins suivants dans ces montants : 5, 5
  • Les 10 produits de type 2 sont distribués aux deux derniers magasins dans ces montants : 5, 5
  • Le nombre maximum de produits offerts à n'importe quel magasin est max(5, 5, 5, 5, 5, 5, 5) = 5.

Exemple 3 :

• Entrée : n = 1, quantités = [100000]
• Sortie : 100000
• Explication : La seule manière optimale est :
  • Les 100000 produits de type 0 sont distribués au seul magasin.
  • Le nombre maximum de produits offerts à un magasin est max(100000) = 100000.

Contraintes :

• m == quantités.longueur
• 1 5
• 1 5

Indice :

1. Il existe une nature monotone telle que lorsque x est inférieur à un certain nombre, il n'y aura aucun moyen de distribuer, et lorsque x n'est pas inférieur à ce nombre, il y aura toujours un moyen de distribuer.
2. Si on vous donne un nombre k, où le nombre de produits donnés à un magasin ne dépasse pas k, pourriez-vous déterminer si tous les produits peuvent être distribués ?
3. Implémentez une fonction canDistribute(k), qui renvoie vrai si vous pouvez distribuer tous les produits de telle sorte qu'aucun magasin ne reçoive pas plus de k produits, et renvoie faux si vous ne le pouvez pas. Utilisez cette fonction pour rechercher binairement le plus petit k possible.

Solution :

Nous pouvons utiliser une recherche binaire sur le nombre maximum possible de produits attribués à n'importe quel magasin (x). Voici une explication étape par étape et la solution PHP :

Approche

1. Configuration de la recherche binaire :

   • Définissez la limite inférieure (à gauche) sur 1 (puisque chaque magasin peut obtenir au moins 1 produit).
   • Définissez la limite supérieure (à droite) comme quantité maximale dans le tableau de quantités (dans le pire des cas, un magasin obtient tous les produits d'un type).
   • Notre objectif est de minimiser la valeur de x (produits maximum donnés à n'importe quel magasin).

2. Logique de recherche binaire :

   • Pour chaque point médian x, vérifiez s'il est possible de distribuer tous les produits de telle sorte qu'aucun magasin n'ait plus de x produits.
   • Utilisez une fonction d'assistance canDistribute(x) pour déterminer la faisabilité.

3. Vérification de faisabilité (canDistribute) :

   • Pour chaque type de produit en quantités, calculez le nombre minimum de magasins nécessaires pour distribuer ce type de produit sans dépasser x produits par magasin.
   • Sommez les magasins requis pour tous les types de produits.
   • Si le total des magasins requis est inférieur ou égal à n, la répartition est possible avec x comme charge maximale par magasin ; sinon, ce n'est pas réalisable.

4. Ajustement de la recherche binaire :

   • Si canDistribute(x) renvoie vrai, cela signifie que x est une solution réalisable, mais nous voulons minimiser x, alors ajustez la limite droite.
   • S'il renvoie faux, augmentez la limite gauche car x est trop petit.

5. Résultat :

   • Une fois la recherche binaire terminée, la gauche contiendra le minimum x possible.

Implémentons cette solution en PHP : 2064. Maximum minimisé de produits distribués dans n'importe quel magasin

<?php /**
 * @param Integer $n
 * @param Integer[] $quantities
 * @return Integer
 */
function minimizedMaximum($n, $quantities) {    
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Helper function to check if we can distribute products with maximum `x` per store
 *
 * @param $x
 * @param $quantities
 * @param $n
 * @return bool
 */
function canDistribute($x, $quantities, $n) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo minimizedMaximum(6, [11, 6]); // Output: 3
echo minimizedMaximum(7, [15, 10, 10]); // Output: 5
echo minimizedMaximum(1, [100000]); // Output: 100000
?>

Explication:

1. Fonction canDistribute :

   • Pour chaque quantité, il calcule le nombre minimum de magasins requis en divisant la quantité par x (en utilisant le plafond pour arrondir puisque chaque magasin peut obtenir un nombre entier de produits).
   • Il renvoie false si les magasins cumulés requis dépassent n.

2. Recherche binaire sur x :

   • La recherche binaire réduit de manière itérative la plage de x jusqu'à ce qu'elle converge vers la valeur minimale réalisable.

3. Efficacité :

   • Cette solution est efficace pour les grandes tailles d'entrée (n et m jusqu'à 10^5) car la recherche binaire s'exécute en O(log(max_quantity) * m), ce qui est réalisable dans les limites données.

Cette approche minimise x, garantissant que les produits sont répartis aussi uniformément que possible dans les magasins.

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!