Prenez des cadeaux de la pile la plus riche

2558. Prenez des cadeaux de la pile la plus riche

Difficulté :Facile

Sujets : Tableau, tas (file d'attente prioritaire), simulation

Vous recevez un tableau de cadeaux entiers indiquant le nombre de cadeaux répartis dans différentes piles. Chaque seconde, vous effectuez les opérations suivantes :

• Choisissez la pile avec le nombre maximum de cadeaux.
• S'il y a plus d'une pile avec le nombre maximum de cadeaux, choisissez-en une.
• Laissez derrière vous le plancher de la racine carrée du nombre de cadeaux dans la pile. Prenez le reste des cadeaux.

Renvoyer le nombre de cadeaux restants après k secondes.

Exemple 1 :

• Entrée : cadeaux = [25,64,9,4,100], k = 4
• Sortie : 29
• Explication : Les cadeaux sont pris de la manière suivante :
  • Dans la première seconde, la dernière pile est choisie et 10 cadeaux sont laissés derrière.
  • Ensuite, la deuxième pile est choisie et 8 cadeaux sont laissés derrière.
  • Après cela, la première pile est choisie et 5 cadeaux sont laissés derrière.
  • Enfin, la dernière pile est à nouveau choisie et 3 cadeaux restent.
  • Les derniers cadeaux restants sont de [5,8,9,4,3], donc le nombre total de cadeaux restants est de 29.

Exemple 2 :

• Entrée : cadeaux = [1,1,1,1], k = 4
• Sortie : 4
• Explication : Dans ce cas, quelle que soit la pile que vous choisissez, vous devez laisser derrière vous 1 cadeau dans chaque pile.
  • C'est-à-dire que vous ne pouvez emporter aucune pile avec vous.
  • Donc, le total des cadeaux restants est de 4.

Contraintes :

• 1 <= cadeaux.longueur <= 10³
• 1 <= cadeaux[i] <= 10⁹
• 1 <= k <= 10³

Indice :

1. Comment pouvez-vous suivre les plus gros cadeaux de la gamme
2. Quel est le moyen efficace de trouver la racine carrée d'un nombre ?
3. Pouvez-vous continuer à additionner les valeurs des cadeaux tout en vous assurant qu'ils sont dans un certain ordre ?
4. Pouvons-nous utiliser une file d'attente ou un tas prioritaire ici ?

Solution :

Nous pouvons utiliser un tas maximum (file d'attente prioritaire) car nous devons sélectionner à plusieurs reprises la pile avec le nombre maximum de cadeaux. Un tas maximum nous permettra d'accéder efficacement à la plus grande pile en temps constant et de mettre à jour le tas après avoir retiré les cadeaux de la pile.

Approche:

1. Utilisez un tas maximum :

   • Puisque nous devons obtenir à plusieurs reprises la pile avec le nombre maximum de cadeaux, un tas maximum (file d'attente prioritaire) est idéal. En PHP, nous pouvons utiliser SplPriorityQueue, qui est une file d'attente prioritaire qui fonctionne par défaut comme un tas maximum.
   • Pour simuler un max-heap, nous insérerons le nombre de cadeaux comme valeur négative, puisque SplPriorityQueue est un min-heap par défaut. En insérant des valeurs négatives, la plus petite valeur négative représentera le plus grand nombre d'origine.

2. Traitement chaque seconde :

   • À chaque seconde, faites éclater la pile avec le nombre maximum de cadeaux du tas.
   • Prenez tous les cadeaux sauf le plancher de la racine carrée du nombre de cadeaux dans cette pile.
   • Repoussez la pile modifiée dans le tas.

3. Résiliation :

   • On s'arrête après k secondes ou une fois qu'on a traité toutes les secondes.

Implémentons cette solution en PHP : 2558. Prenez des cadeaux de la pile la plus riche

<?php
/**
 * @param Integer[] $gifts
 * @param Integer $k
 * @return Integer
 */
function pickGifts($gifts, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$gifts1 = [25, 64, 9, 4, 100];
$k1 = 4;
echo pickGifts($gifts1, $k1) . "\n"; // Output: 29

$gifts2 = [1, 1, 1, 1];
$k2 = 4;
echo pickGifts($gifts2, $k2) . "\n"; // Output: 4
?>




<h3>
  
  
  Explication:
</h3>

<ol>
<li>
<p><strong>Initialisation du tas</strong> :</p>

<ul>
<li>
SplPriorityQueue est utilisé pour simuler un tas maximum. La méthode insert nous permet de pousser des éléments dans le tas avec une priorité.</li>
</ul>
</li>
<li>
<p><strong>Traitement du plus gros tas</strong> :</p>

<ul>
<li>Pour k itérations, le plus gros tas est extrait à l'aide de l'extrait.</li>
<li>Le nombre de cadeaux laissés derrière est calculé comme le plancher de la racine carrée de la plus grande pile actuelle en utilisant floor(sqrt(...)).</li>
<li>Le tas réduit est réinséré dans le tas.</li>
</ul>
</li>
<li>
<p><strong>Résumation des cadeaux restants</strong> :</p>

<ul>
<li>Après les k opérations, tous les éléments du tas sont extraits et additionnés pour obtenir le nombre total de cadeaux restants.</li>
</ul>
</li>
<li>
<p><strong>Cas Edge</strong> :</p>

<ul>
<li>Si les cadeaux sont vides, le résultat est 0.</li>
<li>Si k est supérieur au nombre d'opérations possibles, l'algorithme le gère gracieusement.</li>
</ul>
</li>
</ol>

<h3>
  
  
  Complexité temporelle :
</h3>

<ul>
<li>
<strong>Opérations sur le tas (insertion et extraction)</strong> : Chaque opération sur le tas (insertion et extraction) prend <em><strong>O(log n)</strong></em>, où <em><strong>n</strong></em> est le nombre de pieux.</li>
<li>
<strong>Bouclage à travers k opérations</strong> : Nous effectuons <em><strong>k</strong></em> opérations, chacune impliquant une extraction et une insertion de tas, toutes deux prenant <em><strong>O(log n)</strong></em>.</li>
</ul>

<p>Ainsi, la complexité temporelle totale est <em><strong>O(k log n)</strong></em>, où <em><strong>n</strong></em> est le nombre de piles et <em><strong>k</strong></em> est le nombre de secondes.</p>

<h3>
  
  
  Exemple de procédure pas à pas :
</h3>

<p>Pour la saisie :<br>
</p>
<pre class="brush:php;toolbar:false"><?php
/**
 * @param Integer[] $gifts
 * @param Integer $k
 * @return Integer
 */
function pickGifts($gifts, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$gifts1 = [25, 64, 9, 4, 100];
$k1 = 4;
echo pickGifts($gifts1, $k1) . "\n"; // Output: 29

$gifts2 = [1, 1, 1, 1];
$k2 = 4;
echo pickGifts($gifts2, $k2) . "\n"; // Output: 4
?>

1. Au départ, la file d'attente prioritaire a les piles : [25, 64, 9, 4, 100].
2. Après 1 seconde : choisissez 100, laissez-en 10 derrière vous. Les cadeaux restants sont : [25, 64, 9, 4, 10].
3. Après 2 secondes : choisissez 64, laissez-en 8 derrière vous. Les cadeaux restants sont : [25, 8, 9, 4, 10].
4. Après 3 secondes : choisissez-en 25, laissez-en 5 derrière vous. Les cadeaux restants sont : [5, 8, 9, 4, 10].
5. Après 4 secondes : choisissez-en 10, laissez-en 3 derrière vous. Les cadeaux restants sont : [5, 8, 9, 4, 3].

La somme des cadeaux restants est 5 8 9 4 3 = 29.

Cette approche résout efficacement le problème en utilisant un tas maximum et fonctionne bien dans les limites des contraintes données.

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!