Finden Sie den Schüler, der die Kreide ersetzen wird

1894. Finden Sie den Schüler, der die Kreide ersetzen wird

Schwierigkeit:Mittel

Themen:Array, Binäre Suche, Simulation, Präfixsumme

Es gibt n Schüler in einer Klasse mit den Nummern 0 bis n – 1. Der Lehrer gibt jedem Schüler eine Aufgabe, beginnend mit der Schülernummer 0, dann mit der Schülernummer 1 usw., bis der Lehrer die Schülernummer n erreicht - 1. Danach startet der Lehrer den Vorgang erneut und beginnt erneut mit der Schülernummer 0.

Sie erhalten ein 0-indiziertes ganzzahliges Array chalk und eine ganze Zahl k. Es sind zunächst k Kreidestücke. Wenn dem Schüler Nummer i ein Problem zur Lösung gegeben wird, verwendet er Kreidestücke, um dieses Problem zu lösen. Wenn jedoch die aktuelle Anzahl an Kreidestücken deutlich kleiner als Kreide[i] ist, dann wird die Schülerzahl aufgefordert, die Kreide zu ersetzen.

Geben Sie den Index des Schülers zurück, der die Kreidestückeersetzen soll.

Beispiel 1:

• Eingabe:Kreide = [5,1,5], k = 22
• Ausgabe: 0
• Erläuterung: Die Schüler gehen abwechselnd wie folgt vor:
  • Schüler Nummer 0 verwendet 5 Kreide, also ist k = 17.
  • Schüler Nummer 1 verwendet 1 Kreide, also ist k = 16.
  • Schüler Nummer 2 verwendet 5 Kreiden, also ist k = 11.
  • Schüler Nummer 0 verwendet 5 Kreide, also ist k = 6.
  • Schüler Nummer 1 verwendet 1 Kreide, also ist k = 5.
  • Schüler Nummer 2 verwendet 5 Kreiden, also ist k = 0.
  • Schüler Nummer 0 hat nicht genug Kreide, also muss er sie ersetzen.

Beispiel 2:

• Eingabe:Kreide = [3,4,1,2], k = 25
• Ausgabe: 1
• Erläuterung: Die Schüler gehen abwechselnd wie folgt vor:
  • Schüler Nummer 0 verwendet 3 Kreiden, also ist k = 22.
  • Schüler Nummer 1 verwendet 4 Kreiden, also k = 18.
  • Schüler Nummer 2 verwendet 1 Kreide, also ist k = 17.
  • Schüler Nummer 3 verwendet 2 Kreiden, also k = 15.
  • Schüler Nummer 0 verwendet 3 Kreiden, also ist k = 12.
  • Schüler Nummer 1 verwendet 4 Kreiden, also ist k = 8.
  • Schüler Nummer 2 verwendet 1 Kreide, also ist k = 7.
  • Schüler Nummer 3 verwendet 2 Kreiden, also ist k = 5.
  • Schüler Nummer 0 verwendet 3 Kreiden, also ist k = 2.
  • Schüler Nummer 1 hat nicht genug Kreide, also muss er sie ersetzen.

Einschränkungen:

• chalk.length == n
• 1 <= n <= 10₅
• 1 <= Kreide[i] <= 10₅
• 1 <= k <= 10₉

Hinweis:

1. Subtrahieren Sie die Summe der Kreide von k, bis k kleiner als die Summe der Kreide ist.
2. Jetzt iterieren Sie über das Array. Wenn chalk[i] kleiner als k ist, ist dies die Antwort. Ansonsten subtrahiere chalk[i] von k und fahre fort.

Lösung:

Lassen Sie uns das Problem Schritt für Schritt aufschlüsseln:

Ansatz:

1. Gesamtkreideverbrauch:
   Berechnen Sie zunächst die Gesamtmenge an Kreide, die für eine komplette Runde benötigt wird (von Schüler 0 bis Schüler n-1). Dies hilft uns, den Wert von k zu reduzieren, indem berücksichtigt wird, wie viele vollständige Runden mit k Kreidestücken abgedeckt werden können.

2. Reduzieren Sie k um Modulo:
   Wenn k größer ist als die gesamte Kreide, die für eine vollständige Runde benötigt wird, können wir das Problem vereinfachen, indem wir k % total_chalk nehmen. Durch diesen Vorgang erhalten wir die verbleibende Kreide nach so vielen vollständigen Runden wie möglich, sodass wir nur noch ein kleineres Problem lösen müssen.

3. Finden Sie den Schüler, dem die Kreide ausgeht:
   Durchlaufen Sie den Kreideverbrauch jedes Schülers und subtrahieren Sie ihn von k, bis k kleiner wird als der Kreidebedarf des aktuellen Schülers. Der Index dieses Schülers ist unsere Antwort.

Beispielhafte Vorgehensweise:

Nehmen wir ein Beispiel: Kreide = [3, 4, 1, 2] und k = 25:

1. Gesamtkreideverbrauch:

   text{total_chalk} = 3 + 4 + 1 + 2 = 10

1. Reduzieren Sie k:

   k % 10 = 25 % 10 = 5

Jetzt haben wir k = 5, nachdem wir so viele volle Runden wie möglich subtrahiert haben.

1. Studenten finden:
   • Schüler 0 verwendet 3 Kreiden, also ist k = 5 - 3 = 2.
   • Schüler 1 benötigt 4 Kreide, aber k = 2, was weniger als 4 ist.
   • Daher ist Schüler 1 derjenige, der die Kreide ersetzen muss.

Lassen Sie uns diese Lösung in PHP implementieren: 1894. Finden Sie den Schüler, der die Kreide ersetzen wird

  
  
  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:




Time Complexity: O(n) — we sum the array and then iterate through it once.

Space Complexity: O(1) — only a few variables are used, independent of the input size.


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:


LinkedIn
GitHub



          

            
  

            
        
Das obige ist der detaillierte Inhalt vonFinden Sie den Schüler, der die Kreide ersetzen wird. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!