代码拉取完成，页面将自动刷新
同步操作将从 doocs/leetcode 强制同步，此操作会覆盖自 Fork 仓库以来所做的任何修改，且无法恢复！！！
确定后同步将在后台操作，完成时将刷新页面，请耐心等待。
一个班级里有 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方法一：前缀和 + 二分查找
以下是二分查找的两个通用模板：
模板 1：
boolean check(int x) {}
int search(int left, int right) {
while (left < right) {
int mid = (left + right) >> 1;
if (check(mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
模板 2：
boolean check(int x) {}
int search(int left, int right) {
while (left < right) {
int mid = (left + right + 1) >> 1;
if (check(mid)) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}
做二分题目时，可以按照以下步骤：
while (left < right)，注意是 left < right，而非 left <= right；mid = (left + right) >> 1；check() 函数（有时很简单的逻辑，可以不定义 check），想一下究竟要用 right = mid（模板 1） 还是 left = mid（模板 2）；
right = mid，那么无脑写出 else 语句 left = mid + 1，并且不需要更改 mid 的计算，即保持 mid = (left + right) >> 1；left = mid，那么无脑写出 else 语句 right = mid - 1，并且在 mid 计算时补充 +1，即 mid = (left + right + 1) >> 1。注意，这两个模板的优点是始终保持答案位于二分区间内，二分结束条件对应的值恰好在答案所处的位置。 对于可能无解的情况，只要判断二分结束后的 left 或者 right 是否满足题意即可。
class Solution:
def chalkReplacer(self, chalk: List[int], k: int) -> int:
s = list(accumulate(chalk))
k %= s[-1]
return bisect_right(s, k)
class Solution {
public int chalkReplacer(int[] chalk, int k) {
int n = chalk.length;
long[] preSum = new long[n + 1];
for (int i = 0; i < n; ++i) {
preSum[i + 1] = preSum[i] + chalk[i];
}
k %= preSum[n];
int left = 0, right = n - 1;
while (left < right) {
int mid = (left + right) >> 1;
if (preSum[mid + 1] > k) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
class Solution {
public:
int chalkReplacer(vector<int>& chalk, int k) {
int n = chalk.size();
vector<long long> s(n, chalk[0]);
for (int i = 1; i < n; ++i) s[i] = s[i - 1] + chalk[i];
k %= s[n - 1];
return upper_bound(s.begin(), s.end(), k) - s.begin();
}
};
func chalkReplacer(chalk []int, k int) int {
n := len(chalk)
s := make([]int, n+1)
for i := 0; i < n; i++ {
s[i+1] = s[i] + chalk[i]
}
k %= s[n]
left, right := 0, n-1
for left < right {
mid := (left + right) >> 1
if s[mid+1] > k {
right = mid
} else {
left = mid + 1
}
}
return left
}
impl Solution {
pub fn chalk_replacer(chalk: Vec<i32>, k: i32) -> i32 {
let pre_sum: Vec<i64> = chalk
.into_iter()
.map(|x| x as i64)
.scan(0, |state, x| {
*state += x;
Some(*state)
})
.collect();
pre_sum
.binary_search(&(k as i64 % pre_sum.last().unwrap()))
.map_or_else(|e| e, |v| v + 1) as i32
}
}
此处可能存在不合适展示的内容，页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容，可点击提交进行申诉，我们将尽快为您处理。