找到将更换粉笔的学生

发布日期： 2024-09-03 阅读量： 作者： 网络

找到将更换粉笔的学生

1894。找到将替换粉笔的学生

难度：中等

主题：数组、二分查找、模拟、前缀和

一个班级有n个学生，编号从0到n - 1。老师会给每个学生一个问题，从学号0开始，然后是学号1，以此类推，直到老师达到学号n - 1. 之后，老师将重新开始该过程，再次从学号0开始。

给你一个0索引整数数组chalk和一个整数k。最初有 k 支粉笔。当编号 i 的学生需要解决一个问题时，他们将使用 chalk[i] 块粉笔来解决该问题。然而，如果当前粉笔的数量严格小于粉笔[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 号学生没有足够的粉笔，所以他们必须更换它。

约束：

提示：

解决方案：

让我们一步步分解问题：

粉笔总消耗量：
首先，计算完整一轮（从学生 0 到学生 n-1）所需的粉笔总量。这将帮助我们通过考虑 k 支粉笔可以覆盖多少完整回合来减少 k 的值。
通过模数减少 k：
如果 k 大于一整轮所需的粉笔总数，我们可以通过取 k %total_chalk 来简化问题。此操作将在尽可能多的整轮后为我们提供剩余的粉笔，留下一个较小的问题需要解决。
找到粉笔用完的学生：
迭代每个学生的粉笔消耗量，从 k 中减去它，直到 k 小于当前学生的粉笔需求。这位同学的索引就是我们的答案。

举个例子，chalk = [3, 4, 1, 2] 且 k = 25：

   text{total_chalk} = 3 + 4 + 1 + 2 = 10

随便看看