🔗 🟡 1894. Find the Student that Will Replace the Chalk 1356

tags: `Biweekly Contest 54` `陣列(Array)` `模擬(Simulation)` `前綴和(Prefix Sum)` `二分搜尋(Binary Search)`

題意

一個班級中有 $n$ 個學生，編號從 $0$ 到 $n - 1$ 。老師會從學生編號 $0$ 開始給每個學生一個問題，然後是學生編號 $1$ ，依此類推，直到老師到達學生編號 $n - 1$ 。之後，老師會重新開始這個過程，再次從學生編號 $0$ 開始。

給定一個長度為 $n$ 且下標從 $0$ 開始的整數陣列 $chalk$ 和一個整數 $k$ 。其中 $k$ 表示一開始的粉筆數量，而 $chalk[i]$ 表示學生編號 $i$ 會使用 $chalk[i]$ 個粉筆來解決問題。當粉筆數量嚴格少於 $chalk[i]$ 時，則學生編號 $i$ 將被要求補充粉筆。

返回需要補充粉筆的學生編號。

思路

方法一：模擬(Simulation)

由於每一輪消耗的粉筆數量為 $total = \displaystyle\sum_{i=0}^{n-1} chalk[i]$ ，因此可以使用模運算來減少計算量，即 $k^{\prime} = k \bmod total$ 。這樣可以確保我們只需要考慮一輪內的情況。

在處理完 $k$ 之後，直接模擬最後一輪的分發過程即可。以 $k^{\prime}$ 表示剩餘的粉筆數量，當 $k^{\prime} < chalk[i]$ 時，表示第 $i$ 個學生需要補充粉筆，返回 $i$ ，否則就減去 $chalk[i]$ 再遍歷下一個學生。

複雜度分析

時間複雜度： $\mathcal{O}(n)$ ，其中 $n$ 是學生的數量。需要遍歷一次 chalk 陣列來計算總和，然後最多再遍歷一次來找到需要補充粉筆的學生。
空間複雜度： $\mathcal{O}(1)$ ，不考慮輸出入的空間。

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

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

方法二：前綴和(Prefix Sum) + 二分搜尋(Binary Search)

同樣只考慮最後一輪的情況，但反過來考慮被消耗的粉筆數量，令在最後一輪中輪到第 $i$ 個學生時，消耗的粉筆數量為 $s[i]$ ，則 $s[i] = \displaystyle\sum_{j=0}^{i} chalk[j]$ ，即 $chalk$ 的前綴和(Prefix Sum) 。

由於剩餘的粉筆數量為 $k^{\prime} = k \bmod total$ ，因此當 $s[i] > k^{\prime}$ 時，表示第 $i$ 個學生需要補充粉筆。由於 $s[i]$ 是單調遞增的，因此可以使用二分搜尋(Binary Search) 來找到 $i$ 。

在 Python 中，可以使用 bisect.bisect_right；在 C++ 中，則使用 std::upper_bound。

複雜度分析

時間複雜度： $\mathcal{O}(n + \log n)$ $O (n + lo g n)$ ，其中 $n$ $n$ 是學生的數量。
- 計算前綴和需要 $O(n)$ 時間。
- 二分搜尋需要 $O(\log n)$ 時間。
空間複雜度： $\mathcal{O}(n)$ ，如果直接修改原陣列，則只需要 $O(1)$ 的空間（不考慮輸出入的空間）。

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(vector<int>& chalk, int k) {
        int n = chalk.size();
        vector<long long> s(n + 1);
        for (int i = 0; i < n; ++i) s[i + 1] = s[i] + chalk[i];
        return upper_bound(s.begin(), s.end(), k % s[n]) - s.begin() - 1;
    }
};