🔗 🟢 1103. Distribute Candies to People 1187

tags: `Weekly Contest 143` `模擬(Simulation)` `數學(Math)`

題意

給定兩個整數 $candies$ 和 $n = num\_people$ ，表示糖果數量和人數。依照以下規則分配糖果：

給第一個人 $1$ 顆糖果，第二個人 $2$ 顆，依此類推，直到第 $n$ 個人得到 $n$ 顆糖果。
然後，回到第一個人，給第一個人 $n + 1$ 顆糖果，第二個人 $n + 2$ 顆，依此類推，直到第 $n$ 個人得到 $2n$ 顆糖果。
重複上述過程，直到糖果分配完畢。如果糖果不夠，則剩下的糖果都給最後一個人。

請求出每個人最後得到的糖果數量。

約束條件

$1 \leq \text{candies} \leq 10^9$
$1 \leq n \leq 1000$

思路：模擬(Simulation) / 數學(Math)

雖然 $\text{candies}$ 的數量可以到 $10^9$ ，但是分配糖果的次數是 $\mathcal{O}(\sqrt{\text{candies}})$ 級別的，因此可以直接模擬分配的過程。此外，也可以根據數學公式計算出每個人最後得到的糖果數量。。

方法一：模擬(Simulation)

按照題意模擬每次的分配過程，直到糖果分配完畢。

具體步驟如下：

初始化一個長度為 $n$ 的陣列 $ans$ ，每個元素初始化為 $0$ 。
維護一個變數 $i$ 表示當前是第幾次分配糖果，初始化為 $0$ 。
使用 while 循環，不斷分配糖果，直到糖果數量 candies 為 0。
在第 $i$ 次分配時，將 $i + 1$ 顆糖果分配給第 $i \bmod n$ 個人。若剩餘糖果數量 $candies < i + 1$ ，則分配剩餘的糖果，並結束分配。
減少 $candies$ 的數量，並增加 $i$ 。
返回最終的糖果分配陣列 $ans$ 。

複雜度分析

時間複雜度： $\mathcal{O}(n + \sqrt{candies})$ $O (n + c an d i es)$ ，其中 $candies$ $c an d i es$ 表示糖果數量。
- 初始化答案陣列的時間複雜度為 $\mathcal{O}(n)$ 。
- 共需分配 $\mathcal{O}(\sqrt{candies})$ 次糖果，每次分配的時間複雜度為 $\mathcal{O}(1)$ 。具體計算見方法二。
空間複雜度： $\mathcal{O}(n)$ 。

class Solution:
    def distributeCandies(self, candies: int, num_people: int) -> List[int]:
        n = num_people
        ans = [0] * n
        i = 0
        while candies > 0: # 第 i 次分配 i + 1 顆糖果給第 i % n 個人
            ans[i % n] += min(candies, i + 1) 
            candies -= i + 1
            i += 1
        return ans

class Solution {
public:
    vector<int> distributeCandies(int candies, int num_people) {
        int n = num_people;
        vector<int> ans(n, 0);
        int i = 0;
        while (candies > 0) {
            ans[i % n] += min(candies, i + 1);
            candies -= i + 1;
            i++;
        }
        return ans;
    }
};

方法二：數學(Math)

在方法一計算時間複雜度時，提及總共分配的次數為 $\mathcal{O}(\sqrt{candies})$ ，這是因為分配的次數可以被計算出來。令可以完整分配的次數為 $m$ ，推導流程如下：

在第 $m$ 次分配時，總共分配了 $1 + 2 + \cdots + m = \frac{m(m+1)}{2}$ 顆糖果。故 $\frac{m(m+1)}{2} \leq candies$ 。
得到 $m^2 + m - 2 \cdot candies \leq 0$ ，解這個一元二次不等式，得到 $m \leq \frac{-1 + \sqrt{8 \cdot candies + 1}}{2}$ 。
故可以完整分配的次數 $m = \left\lfloor \frac{-1 + \sqrt{8 \cdot candies + 1}}{2} \right\rfloor$ 。

根據可以完整分配的次數 $m$ ，可以得出可以完整分配的輪數 $q$ 及剩下的次數 $r$ ，分別為 $q = \lfloor \frac{m}{n} \rfloor$ 和 $r = m \bmod n$ 。

在完整分配的 $q$ 輪中，對於第 $1$ 個人到第 $n$ 個人，可以計算每個人最後得到的糖果數量：

第 $1$ 個人在前 $q$ 輪中分配到的糖果數量分別為 $1, 1 + n, 1 + 2n, \ldots, 1 + (q-1)n$ ，總共為 $\frac{q \cdot (q - 1)}{2} \cdot n + 1 \cdot q$ 。
第 $2$ 個人在前 $q$ 輪中分配到的糖果數量分別為 $2, 2 + n, 2 + 2n, \ldots, 2 + (q-1)n$ ，總共為 $\frac{q \cdot (q - 1)}{2} \cdot n + 2 \cdot q$ 。
第 $i$ 個人在前 $q$ 輪中分配到的糖果數量分別為 $i, i + n, i + 2n, \ldots, i + (q-1)n$ ，總共為 $\frac{q \cdot (q - 1)}{2} \cdot n + i \cdot q$ 。

最後考慮剩餘 $r$ 次分配的情況：

對於第 $1$ 個人，若在第 $q+1$ 輪中也能被完整分配，則其在第 $q+1$ 輪中分配到的糖果數量為 $q \cdot n + 1$ 。
對於第 $i$ 個人，若在第 $q+1$ 輪中也能被完整分配，則其在第 $q+1$ 輪中分配到的糖果數量為 $q \cdot n + i$ 。
若不能完整分配，則其在第 $q+1$ 輪中分配到的糖果數量為 $candies - \frac{m \cdot (m + 1)}{2}$ 。

具體步驟如下：

計算可以完整分配的次數 $m$ ，以及可以完整分配的輪數 $q$ 和剩下的次數 $r$ 。
初始化一個長度為 $n$ 的陣列 $ans$ ，每個元素初始化為 $0$ 。
遍歷每個人，對於第 $i+1$ $i + 1$ 個人：
- 若 $i < r$ ，則每人應得糖果為 $\frac{q \cdot (q - 1)}{2} \cdot n + (i + 1) \cdot q + (q \cdot n + i + 1)$ 。
- 若 $i = r$ ，則每人應得糖果為 $\frac{q \cdot (q - 1)}{2} \cdot n + (i + 1) \cdot q + (candies - \frac{m \cdot (m + 1)}{2})$ 。
- 若 $i > r$ ，則每人應得糖果為 $\frac{q \cdot (q - 1)}{2} \cdot n + (i + 1) \cdot q$ 。
返回最終的糖果分配陣列 $ans$ 。

複雜度分析

時間複雜度： $\mathcal{O}(n)$ ，其中 $n$ 表示人數。
空間複雜度： $\mathcal{O}(n)$ 。

class Solution:
    def distributeCandies(self, candies: int, num_people: int) -> List[int]:
        n = num_people
        m = int((-1 + sqrt(8 * candies + 1)) / 2) # 可以分配 m 次
        q, r = divmod(m, n) # 可以完整分配 q 輪，剩下 r 個
        ans = [0] * n
        for i in range(n):
            ans[i] =  q * (q - 1) // 2 * n + q * (i + 1)
            if i < r:
                ans[i] += q * n + i + 1
            elif i == r:
                ans[i] += candies - m * (m + 1) // 2
        return ans

class Solution {
public:
    vector<int> distributeCandies(int candies, int num_people) {
        int n = num_people;
        int m = (-1 + sqrt(8.0 * candies + 1.0)) / 2;
        int q = m / n, r = m % n;
        vector<int> ans(n, 0);
        for (int i = 0; i < n; i++) {
            ans[i] = q * (q - 1) / 2 * n + q * (i + 1);
            if (i < r) ans[i] += q * n + i + 1;
            else if (i == r) ans[i] += candies - m * (m + 1) / 2;
        }
        return ans;
    }
};