題目： 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;
}
};
|
