Maison > Article > développement back-end > Trouvez l'élève qui remplacera la craie
1894. Trouvez l'élève qui remplacera la craie
Difficulté :Moyen
Sujets : Tableau, recherche binaire, simulation, somme de préfixes
Il y a n élèves dans une classe numérotés de 0 à n - 1. Le professeur donnera à chaque élève un problème en commençant par l'élève numéro 0, puis l'élève numéro 1, et ainsi de suite jusqu'à ce que l'enseignant atteigne le numéro d'élève n. - 1. Après cela, l'enseignant redémarrera le processus en commençant à nouveau par l'élève numéro 0.
Vous recevez une craie de tableau d'entiers indexés à 0 et un k entier. Il y a initialement k morceaux de craie. Lorsque l'élève numéro i se voit confier un problème à résoudre, il utilisera des morceaux de craie [i] pour résoudre ce problème. Cependant, si le nombre actuel de morceaux de craie est strictement inférieur à la craie[i], alors il sera demandé au numéro d'élève i de remplacer la craie.
Renvoyer l'index de l'élève qui remplacera les morceaux de craie.
Exemple 1 :
Exemple 2 :
Contraintes :
Indice :
Solution :
Décomposons le problème étape par étape :
Consommation totale de craie :
Tout d’abord, calculez la quantité totale de craie nécessaire pour un tour complet (de l’élève 0 à l’élève n-1). Cela nous aidera à réduire la valeur de k en tenant compte du nombre de tours complets qui peuvent être couverts par k morceaux de craie.
Réduire k par Modulo :
Si k est plus grand que le total de craie requis pour un tour complet, nous pouvons simplifier le problème en prenant k % total_chalk. Cette opération nous donnera la craie restante après autant de tours complets que possible, nous laissant avec un plus petit problème à résoudre.
Trouvez l'élève qui manque de craie :
Parcourez la consommation de craie de chaque élève, en la soustrayant de k jusqu'à ce que k devienne inférieur aux besoins en craie de l'élève actuel. L'index de cet élève est notre réponse.
Prenons un exemple craie = [3, 4, 1, 2] et k = 25 :
text{total_chalk} = 3 + 4 + 1 + 2 = 10
k % 10 = 25 % 10 = 5
Maintenant, nous avons k = 5 après avoir soustrait autant de tours complets que possible.
Implémentons cette solution en PHP : 1894. Trouvez l'élève qui remplacera la craie
Explanation:
- Total Chalk Sum: We sum up all the chalk requirements to get the total for one complete round.
- Modulo Operation: Using modulo with k, we get the effective number of chalks to distribute after full rounds.
- Find the Student: We then iterate through the students, checking if the remaining chalk is sufficient. The first time it's insufficient, that student's index is the answer.
Complexity:
This approach ensures that the problem is solved efficiently even for large inputs.
Contact Links
If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks ?. Your support would mean a lot to me!
If you want more helpful content like this, feel free to follow me:
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!