1894.找到需要补充粉笔的学生编号

方法一：优化的模拟

思路与算法：先求出一轮消耗的粉笔总数total，将粉笔数量k对total进行取模，求得余数一定小于total，因此只需遍历一次数组chalk即可求出学生编号。

class Solution {
    public int chalkReplacer(int[] chalk, int k) {
        int n = chalk.length;
        long total = 0;
        for (int num : chalk) {
            total += num;
        }
        k %= total;
        int res = -1;
        for (int i = 0; i < n; ++i) {
            if (chalk[i] > k) {
                res = i;
                break;
            }
            k -= chalk[i];
        }
        return res;
    }
}

方法二：前缀和 + 二分查找

思路与算法：对于方法一中的第二次遍历，我们也可以使用二分查找进行加速。

在对数组chalk 的遍历过程中，我们可以求出其前缀和，记为数组pre。那么需要补充粉笔的学生编号$i’$是最小的满足 $\textit{pre}[i] > k’$的下标$i’$可以通过二分查找在$ O(\log n)$ 的时间内找出。

class Solution {
    public int chalkReplacer(int[] chalk, int k) {
        int n = chalk.length;
        if (chalk[0] > k) {
            return 0;
        }
        for (int i = 1; i < n; ++i) {
            chalk[i] += chalk[i - 1];
            if (chalk[i] > k) {
                return i;
            }
        }

        k %= chalk[n - 1];
        return binarySearch(chalk, k);
    }

    public int binarySearch(int[] arr, int target) {
        int low = 0, high = arr.length - 1;
        while (low < high) {
            int mid = (high - low) / 2 + low;
            if (arr[mid] <= target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }
}

细节：在求total时可能产生溢出，需使用long来定义total；