題目： LeetCode - 1103. Distribute Candies to People

題目說明

給兩個整數，candies 表示糖果的數量，num_people 表示糖果要分給的人數。分糖果的規則為

1
2
3
4
5
6
7
8
9
10
num_people =  4
candies    = 40
     i:   0  1  2  3
people:   1  2  3  4
----------------------
round 1   1  2  3  4      每個人分到的糖果數： i + 1 + 0 * num_people
round 2   5  6  7  8      每個人分到的糖果數： i + 1 + 1 * num_people
round 3   4               每個人分到的糖果數： i + 1 + 2 * num_people 當糖果數量不夠時就全部給當前的那個人即可
----------------------
         10  8 10 12

回傳一個代表每個人收到糖果數量的陣列。

解題思路

可以直接模擬每次發放糖果的情況，但是效率較低，我們可以使用等差數列總和的公式計算每輪的糖果數量，最後剩下的糖果在模擬發放的過程即可。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<int> distributeCandies(int candies, int num_people) {
        int r = 0, tmp;
        vector<int> v(num_people);
        while(candies >= (tmp = (1 + num_people) * num_people / 2 + num_people * num_people * r)) candies -= tmp, ++r;
        if(r) for(int i = 0; i < num_people; ++i) v[i] += (i + 1 + i + 1 + num_people * (r - 1)) * r / 2;
        for(int i = 0; i < num_people; ++i)
            if(candies >= (tmp = i + 1 + num_people * r)) v[i] += tmp, candies -= tmp;
            else { v[i] += candies; break; }
        return v;
    }
};