厦门集美区网站建设,职业生涯规划ppt免费模板,app页面模板,杭州公司注册地址租赁1894. 找到需要补充粉笔的学生编号
一个班级里有 n 个学生#xff0c;编号为 0 到 n - 1 。每个学生会依次回答问题#xff0c;编号为 0 的学生先回答#xff0c;然后是编号为 1 的学生#xff0c;以此类推#xff0c;直到编号为 n - 1 的学生#xff0c;然后老师会重复…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 的学生没有足够的粉笔所以他需要补充粉笔。
解题思路
使用前缀和二分
我们可以通过维护一个前缀和数组记录下当遍历到当前学生A的时候已经消耗了多少根粉笔因为chalk数组是需要循环遍历的所以当chalk数组的总和小于k的时候我们可以直接将k将去chalk数组的总和当作已经遍历了一轮了粉笔还没消耗完。我们可以通过取模直接避免这种循环遍历使用二分法查找前缀和小于k的下标说明遍历到当前学生的时候粉笔已经用完了
代码
class Solution {public int chalkReplacer(int[] chalk, int k) {int nchalk.length;long[] dpnew long[n1];for(int i0;in;i)dp[i1]dp[i]chalk[i];long tark%dp[n];int l0,rn;while(lr){int mid(r-l)/2l;if(dp[mid]tar){rmid-1;}else lmid1;}return l-1;}
}
