Divisez les joueurs en équipes de compétences égales

2491. Divisez les joueurs en équipes de compétences égales

Difficulté :Moyen

Sujets : Tableau, table de hachage, deux pointeurs, tri

Vous recevez un tableau de compétences de tableau d'entiers positifs de pair longueur n où compétence[i] désigne la compétence du i^ème joueur. Répartissez les joueurs en n/2 équipes de taille 2 de telle sorte que la compétence totale de chaque équipe soit égale.

La chimie d'une équipe est égale au produit des compétences des joueurs de cette équipe.

Renvoyer la somme de la chimie de toutes les équipes, ou renvoyer -1 s'il n'y a aucun moyen de diviser les joueurs en équipes de telle sorte que la compétence totale de chaque équipe soit égale.

Exemple 1 :

• Entrée : compétence = [3,2,5,1,3,4]
• Sortie : 22
• Explication :
  • Répartissez les joueurs dans les équipes suivantes : (1, 5), (2, 4), (3, 3), où chaque équipe a une compétence totale de 6.
  • La somme de la chimie de toutes les équipes est : 1 * 5 2 * 4 3 * 3 = 5 8 9 = 22.

Exemple 2 :

• Entrée : compétence = [3,4]
• Sortie : 112
• Explication :
  • Les deux joueurs forment une équipe avec une compétence totale de 7.
  • La chimie de l'équipe est de 3 * 4 = 12.

Exemple 3 :

• Entrée : compétence = [1,1,2,3]
• Sortie : -1
• Explication : Il n'y a aucun moyen de diviser les joueurs en équipes de telle sorte que la compétence totale de chaque équipe soit égale.

Contraintes :

• 2 <= compétence.longueur <= 10⁵
• skills.length est pair.
• 1 <= compétence[i] <= 1000

Indice :

1. Essayez de trier le tableau de compétences.
2. Il est toujours optimal d'associer le joueur disponible le plus faible avec le joueur disponible le plus fort.

Solution :

Nous pouvons suivre l'indice fourni et utiliser une approche gourmande. Voici la répartition détaillée de la solution :

Mesures:

1. Trier le tableau de compétences : Le tri nous permet d'associer efficacement le joueur le plus faible (la plus petite valeur) au joueur le plus fort (la plus grande valeur).

2. Vérifier les appariements valides : La somme des compétences de chaque équipe doit être égale. Après le tri, nous associerons le plus petit et le plus grand élément, puis le deuxième plus petit avec le deuxième plus grand, et ainsi de suite. Si à un moment donné, la somme d'une paire diffère des sommes précédentes, il est impossible de diviser les joueurs en équipes valides, et nous devrions renvoyer -1.

3. Calculer la chimie : La chimie de chaque équipe est le produit des deux compétences de cette équipe. Résumez toutes les valeurs de chimie pour chaque équipe valide.

4. Renvoyer la chimie totale : Si toutes les équipes ont la même compétence totale, renvoyez la somme de leur chimie.

Implémentons cette solution en PHP : 2491. Divisez les joueurs en équipes de compétences égales

/**


@param Integer[] $skill
@return Integer
/
function dividePlayers($skill) {
...
...
...
/*


go to ./solution.php
*/
}





// Test cases

$skill1 = [3, 2, 5, 1, 3, 4];

$skill2 = [3, 4];

$skill3 = [1, 1, 2, 3];

echo dividePlayers($skill1) . "\n";  // Output: 22

echo dividePlayers($skill2) . "\n";  // Output: 12

echo dividePlayers($skill3) . "\n";  // Output: -1

?>





  

  

  Explication :




Tri : La compétence de tableau est triée pour garantir que nous pouvons associer efficacement les valeurs les plus petites et les plus grandes.
Deux pointeurs : Nous utilisons deux pointeurs ($i en commençant par le début et $j en commençant par la fin). Pour chaque paire valide (la plus petite et la plus grande), nous vérifions si leur somme est la même que la teamSkillSum attendue. Sinon, il est impossible de répartir les joueurs en équipes.
Calcul de chimie : Si la paire est valide, la chimie est calculée comme le produit des deux valeurs ($skill[$i] * $skill[$j]), et nous continuez à l’ajouter à la chimie totale.

Cas Edge :


Si l'équipe ne peut être constituée en raison de sommes inégales, on rend -1.
Le code gère les cas de longueur égale et garantit que tous les joueurs sont correctement jumelés.





  
  
  Complexité temporelle :



Le tri du tableau prend O(n log n), et le parcours à deux pointeurs prend O(n). Par conséquent, la complexité temporelle globale est O(n log n), ce qui est efficace compte tenu des contraintes.


Cette solution fonctionne dans la limite donnée de jusqu'à 105 joueurs.

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!