一个班级里有 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 的学生没有足够的粉笔，所以他需要补充粉笔。
提示：
chalk.length == n1 <= n <= 1051 <= chalk[i] <= 1051 <= k <= 109
Related Topics
题解
9月10日的每日一题，思路很简单
首先需要知道每个人的时候一共花费了多少粉笔，自然就会想到了前缀和。
再接下来就是按照题面一轮结束，再次从头开始，很自然的就是应该拿总数余上一轮结束总共花费的粉笔数量。
余下的余数则必然会在本轮内消耗完毕，那么就是前面的前缀和数组中找到提问到哪个学生的时候会消耗完毕。那么就是下一个学生来换粉笔了。由于前缀和数组是稳定递增的，所以查找这块的话也自然的想到的是二分查找。
class Solution {
public int chalkReplacer(int[] chalk, int k) {
long [] preSum = new long[chalk.length];
preSum[0] = chalk[0];
//前缀和数组构建，表名了一轮循环下来，第n个学生的时候一共消耗了preSum[n]个粉笔
for (int i = 1; i < chalk.length; i++) {
preSum[i] = (long)chalk[i] + preSum[i-1];
}
//最后一轮需要换粉笔的时候，这一轮开始还剩余chalkLeft支粉笔
long chalkLeft = k % preSum[preSum.length-1];
//拿chalkLeft 用二分法到 preSum 中找到 需要换粉笔的那个学生
int left = 0,right = preSum.length-1;
while (left < right){
int mid = left + ( (right - left) >> 1);
if (preSum[mid] <= chalkLeft){
//包含等于的情况，用完的学生不处理，由下一个来的学生发现没有粉笔了处理
left = mid+1;
}else{
right = mid;
}
}
return left;
}
}
发表评论