1894. 找到需要補充粉筆的學生編號

一個班級里有 n 個學生，編號為 0 到 n - 1 。每個學生會依次回答問題，編號為 0 的學生先回答，然后是編號為 1 的學生，以此類推，直到編號為 n - 1 的學生，然后老師會重復這個過程，重新從編號為 0 的學生開始回答問題。

給你一個長度為 n 且下標從 0 開始的整數數組 chalk 和一個整數 k 。一開始粉筆盒里總共有 k 支粉筆。當編號為 i 的學生回答問題時，他會消耗 chalk[i] 支粉筆。如果剩余粉筆數量 嚴格小于 chalk[i] ，那么學生 i 需要 補充 粉筆。

請你返回需要 補充 粉筆的學生 編號 。

示例 1：輸入：chalk = [5,1,5], k = 22
輸出：0
解釋：學生消耗粉筆情況如下：
- 編號為 0 的學生使用 5 支粉筆，然后 k = 17 。
- 編號為 1 的學生使用 1 支粉筆，然后 k = 16 。
- 編號為 2 的學生使用 5 支粉筆，然后 k = 11 。
- 編號為 0 的學生使用 5 支粉筆，然后 k = 6 。
- 編號為 1 的學生使用 1 支粉筆，然后 k = 5 。
- 編號為 2 的學生使用 5 支粉筆，然后 k = 0 。
編號為 0 的學生沒有足夠的粉筆，所以他需要補充粉筆。
示例 2：輸入：chalk = [3,4,1,2], k = 25
輸出：1
解釋：學生消耗粉筆情況如下：
- 編號為 0 的學生使用 3 支粉筆，然后 k = 22 。
- 編號為 1 的學生使用 4 支粉筆，然后 k = 18 。
- 編號為 2 的學生使用 1 支粉筆，然后 k = 17 。
- 編號為 3 的學生使用 2 支粉筆，然后 k = 15 。
- 編號為 0 的學生使用 3 支粉筆，然后 k = 12 。
- 編號為 1 的學生使用 4 支粉筆，然后 k = 8 。
- 編號為 2 的學生使用 1 支粉筆，然后 k = 7 。
- 編號為 3 的學生使用 2 支粉筆，然后 k = 5 。
- 編號為 0 的學生使用 3 支粉筆，然后 k = 2 。
編號為 1 的學生沒有足夠的粉筆，所以他需要補充粉筆。

解題思路

使用前綴和+二分

1. 我們可以通過維護一個前綴和數組，記錄下當遍歷到當前學生A的時候，已經消耗了多少根粉筆
2. 因為chalk數組是需要循環遍歷的，所以當chalk數組的總和小于k的時候，我們可以直接將k將去chalk數組的總和，當作已經遍歷了一輪了粉筆還沒消耗完。我們可以通過取模，直接避免這種循環遍歷
3. 使用二分法查找前綴和小于k的下標，說明遍歷到當前學生的時候，粉筆已經用完了

代碼

class Solution {public int chalkReplacer(int[] chalk, int k) {int n=chalk.length;long[] dp=new long[n+1];for(int i=0;i<n;i++)dp[i+1]=dp[i]+chalk[i];long tar=k%dp[n];int l=0,r=n;while(l<=r){int mid=(r-l)/2+l;if(dp[mid]>tar){r=mid-1;}else l=mid+1;}return l-1;}
}