Question

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

English Version

题目描述

一个班级里有 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 == n
• 1 <= n <= 105
• 1 <= chalk[i] <= 105
• 1 <= k <= 109

解法

方法一：求和取余 + 模拟

由于学生的回答是一轮一轮循环进行的，因此我们可以将所有学生需要消耗的粉笔数加起来，得到一个总数 $s$。然后我们对 $k$ 取 $s$ 的余数，即可知道最后一轮结束后剩余的粉笔数。

接下来，我们只需要模拟最后一轮即可。初始时，剩余的粉笔数为 $k$，编号为 $0$ 的学生开始回答问题。当剩余的粉笔数小于当前学生需要的粉笔数时，当前学生需要补充粉笔，我们直接返回当前学生的编号 $i$ 即可。否则，我们将剩余的粉笔数减去当前学生需要的粉笔数，并将当前学生的编号 $i$ 加一，进行下一次模拟。

时间复杂度 $O(n)$，其中 $n$ 是学生的数量。空间复杂度 $O(1)$。

class Solution:
  def chalkReplacer(self, chalk: List[int], k: int) -> int:
    s = sum(chalk)
    k %= s
    for i, x in enumerate(chalk):
      if k < x:
        return i
      k -= x

class Solution {
  public int chalkReplacer(int[] chalk, int k) {
    long s = 0;
    for (int x : chalk) {
      s += x;
    }
    k %= s;
    for (int i = 0;; ++i) {
      if (k < chalk[i]) {
        return i;
      }
      k -= chalk[i];
    }
  }
}

class Solution {
public:
  int chalkReplacer(vector<int>& chalk, int k) {
    long long s = accumulate(chalk.begin(), chalk.end(), 0LL);
    k %= s;
    for (int i = 0;; ++i) {
      if (k < chalk[i]) {
        return i;
      }
      k -= chalk[i];
    }
  }
};

func chalkReplacer(chalk []int, k int) int {
  s := 0
  for _, x := range chalk {
    s += x
  }
  k %= s
  for i := 0; ; i++ {
    if k < chalk[i] {
      return i
    }
    k -= chalk[i]
  }
}

function chalkReplacer(chalk: number[], k: number): number {
  let s = 0;
  for (const x of chalk) {
    s += x;
  }
  k %= s;
  for (let i = 0; ; ++i) {
    if (k < chalk[i]) {
      return i;
    }
    k -= chalk[i];
  }
}

impl Solution {
  pub fn chalk_replacer(chalk: Vec<i32>, k: i32) -> i32 {
    let mut s: i64 = chalk
      .iter()
      .map(|&x| x as i64)
      .sum();
    let mut k = (k as i64) % s;
    for (i, &x) in chalk.iter().enumerate() {
      if k < (x as i64) {
        return i as i32;
      }
      k -= x as i64;
    }
    0
  }
}