Cari Pelajar yang Akan Menggantikan Kapur

1894. Cari Pelajar yang Akan Menggantikan Kapur

Kesukaran: Sederhana

Topik: Tatasusunan, Carian Perduaan, Simulasi, Jumlah Awalan

Terdapat n murid dalam kelas bernombor 0 hingga n - 1. Guru akan memberikan setiap murid masalah bermula dengan murid nombor 0, kemudian murid nombor 1, dan seterusnya sehingga guru mencapai nombor murid n - 1. Selepas itu, guru akan memulakan semula proses, bermula dengan nombor pelajar 0 semula.

Anda diberi 0-diindeks kapur tatasusunan integer dan integer k. Pada mulanya terdapat k keping kapur. Apabila murid nombor i diberi masalah untuk diselesaikan, mereka akan menggunakan kapur[i] kepingan kapur untuk menyelesaikan masalah tersebut. Walau bagaimanapun, jika bilangan kepingan kapur semasa adalah secara ketat daripada kapur[i], maka nombor pelajar i akan diminta menggantikan kapur itu.

Kembalikan indeks pelajar yang akan menggantikan kepingan kapur.

Contoh 1:

• Input: kapur = [5,1,5], k = 22
• Output: 0
• Penjelasan: Pelajar pergi secara bergilir-gilir seperti berikut:
  • Pelajar nombor 0 menggunakan 5 kapur, jadi k = 17.
  • Pelajar nombor 1 menggunakan 1 kapur, jadi k = 16.
  • Pelajar nombor 2 menggunakan 5 kapur, jadi k = 11.
  • Pelajar nombor 0 menggunakan 5 kapur, jadi k = 6.
  • Pelajar nombor 1 menggunakan 1 kapur, jadi k = 5.
  • Pelajar nombor 2 menggunakan 5 kapur, jadi k = 0.
  • Pelajar nombor 0 tidak mempunyai kapur yang mencukupi, jadi mereka perlu menggantikannya.

Contoh 2:

• Input: kapur = [3,4,1,2], k = 25
• Output: 1
• Penjelasan: Pelajar pergi secara bergilir-gilir seperti berikut:
  • Pelajar nombor 0 menggunakan 3 kapur jadi k = 22.
  • Pelajar nombor 1 menggunakan 4 kapur jadi k = 18.
  • Pelajar nombor 2 menggunakan 1 kapur jadi k = 17.
  • Pelajar nombor 3 menggunakan 2 kapur jadi k = 15.
  • Pelajar nombor 0 menggunakan 3 kapur jadi k = 12.
  • Pelajar nombor 1 menggunakan 4 kapur jadi k = 8.
  • Pelajar nombor 2 menggunakan 1 kapur jadi k = 7.
  • Pelajar nombor 3 menggunakan 2 kapur jadi k = 5.
  • Pelajar nombor 0 menggunakan 3 kapur jadi k = 2.
  • Pelajar nombor 1 tidak mempunyai kapur yang mencukupi, jadi mereka perlu menggantikannya.

Kekangan:

• kapur.panjang == n
• 1 <= n <= 10₅
• 1 <= kapur[i] <= 10₅
• 1 <= k <= 10₉

Petunjuk:

1. Tolak jumlah kapur daripada k sehingga k kurang daripada jumlah kapur.
2. Sekarang lelaran ke atas tatasusunan. Jika kapur [i] kurang daripada k, ini jawapannya. Jika tidak, tolak kapur [i] daripada k dan teruskan.

Penyelesaian:

Jom pecahkan masalah langkah demi langkah:

Pendekatan:

1. Jumlah Penggunaan Kapur:
   Mula-mula, hitung jumlah kapur yang diperlukan untuk satu pusingan lengkap (daripada pelajar 0 kepada pelajar n-1). Ini akan membantu kita mengurangkan nilai k dengan mengambil kira berapa banyak pusingan lengkap boleh diliputi oleh k keping kapur.

2. Kurangkan k dengan Modulo:
   Jika k lebih besar daripada jumlah kapur yang diperlukan untuk satu pusingan lengkap, kita boleh memudahkan masalah dengan mengambil k % jumlah_kapur. Operasi ini akan memberi kita baki kapur selepas pusingan penuh sebanyak mungkin, meninggalkan masalah yang lebih kecil untuk kita selesaikan.

3. Cari Pelajar Yang Kehabisan Kapur:
   Ulangi penggunaan kapur setiap pelajar, tolak daripada k sehingga k menjadi kurang daripada keperluan kapur pelajar semasa. Indeks pelajar ini adalah jawapan kami.

Contoh Panduan:

Mari kita ambil contoh kapur = [3, 4, 1, 2] dan k = 25:

1. Jumlah Penggunaan Kapur:

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

1. Kurangkan k:

   k % 10 = 25 % 10 = 5

Sekarang kita mempunyai k = 5 selepas menolak sebanyak mungkin pusingan penuh.

1. Cari Pelajar:
   • Murid 0 menggunakan 3 kapur, jadi k = 5 - 3 = 2.
   • Pelajar 1 memerlukan 4 kapur, tetapi k = 2, iaitu kurang daripada 4.
   • Oleh itu, pelajar 1 akan menjadi orang yang perlu menggantikan kapur.

Mari laksanakan penyelesaian ini dalam PHP: 1894. Cari Pelajar yang Akan Menggantikan Kapur

  
  
  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



          

            
  

            
        
Atas ialah kandungan terperinci Cari Pelajar yang Akan Menggantikan Kapur. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!