題目: 1894. Find the Student that Will Replace the Chalk
題意:
給定一個整數陣列chalk，以及一個整數k
現場有n個同學，chalk[i]代表i號同學一次用掉幾個粉筆
總共有k個粉筆，若還有粉筆就由0~n-1同學依序使用
求到第幾號同學會沒有粉筆?

方向:
顯然用了幾輪不是重點，重點是在最後一輪誰會沒粉筆
為了求出最後一輪剩幾個粉筆，我們需要得知所有同學總共會用掉多少粉筆
我們可以透過前綴和(prefix sum)的技巧，代表0~i同學共用了多少粉筆

實作:

class Solution {
public:
    int chalkReplacer(vector<int>& chalk, int k) {
        int n = (int)chalk.size();
        // Create prefix sum table
        vector<long long> prefix_sum(n);
        if(n > 0)
            prefix_sum[0] = (long long)chalk[0];
        for(int i = 1; i < n; i++)
            prefix_sum[i] = prefix_sum[i - 1] + (long long)chalk[i];
        
        // The number of chalks at last round
        k = k % prefix_sum[n - 1];
        
        int res = 0;
        for(int i = 0; i < n; i++)
            if(prefix_sum[i] > k)
            {
                res = i;
                break;
            }
        return res;
    }
};

時間複雜度: O(N)，建立prefix sum和尋找result各遍歷N長度
空間複雜度: O(N)，建立N長度的前綴和表

用時: 大約8分鐘
結果:

覆盤:
粗心大意，題目沒讀仔細，以為把粉筆用光的傢伙就要換粉筆，結果其實是下面一位才換粉筆
在第17行寫成if(prefix_sum[i] >= k)，領一個WA(71/72)，可以說是開局第一把就出糗

Follow Up:
可以發現，尋找result時其實可以二分搜(Binary Search)的方法，因為prefix sum一定是個排序好的陣列
二分搜的部分複雜度為O(lgN)，但還要建立前綴和，所以整體複雜度仍是O(N)

    int binarySearch(vector<long long>& arr, int target) {
        int low = 0, high = arr.size() - 1;

        while (low < high) {
            int mid = low + (high - low) / 2;

            if (arr[mid] <= target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }

        return high;
    }