题目描述
We distribute some number of candies
, to a row of n = num_people people in the following way:
We then give 1 candy to the first person, 2 candies to the second person, and so on until we give n
candies to the last person.
Then, we go back to the start of the row, giving n + 1
candies to the first person, n + 2
candies to the second person, and so on until we give 2 * n
candies to the last person.
This process repeats (with us giving one more candy each time, and moving to the start of the row after we reach the end) until we run out of candies. The last person will receive all of our remaining candies (not necessarily one more than the previous gift).
Return an array (of length num_people
and sum candies
) that represents the final distribution of candies.
Example 1:
Input: candies = 7, num_people = 4
Output: [1,2,3,1]
Explanation:
On the first turn, ans[0] += 1, and the array is [1,0,0,0].
On the second turn, ans[1] += 2, and the array is [1,2,0,0].
On the third turn, ans[2] += 3, and the array is [1,2,3,0].
On the fourth turn, ans[3] += 1 (because there is only one candy left), and the final array is [1,2,3,1].
Example 2:
Input: candies = 10, num_people = 3
Output: [5,2,3]
Explanation:
On the first turn, ans[0] += 1, and the array is [1,0,0].
On the second turn, ans[1] += 2, and the array is [1,2,0].
On the third turn, ans[2] += 3, and the array is [1,2,3].
On the fourth turn, ans[0] += 4, and the final array is [5,2,3].
Constraints:
- 1 <= candies <= 10^9
- 1 <= num_people <= 1000
题意:排排坐,分糖果。
我们买了一些糖果 candies
,打算把它们分给排好队的 n = num_people
个小朋友。
给第一个小朋友 1 颗糖果,第二个小朋友 2 颗,依此类推,直到给最后一个小朋友 n
颗糖果。
然后,我们再回到队伍的起点,给第一个小朋友n + 1
颗糖果,第二个小朋友 n + 2
颗,依此类推,直到给最后一个小朋友2 * n
颗糖果。
重复上述过程(每次都比上一次多给出一颗糖果,当到达队伍终点后再次从队伍起点开始),直到我们分完所有的糖果。注意,就算我们手中的剩下糖果数不够(不比前一次发出的糖果多),这些糖果也会全部发给当前的小朋友。
返回一个长度为num_people
、元素之和为 candies
的数组,以表示糖果的最终分发情况(即 ans[i]
表示第i
个小朋友分到的糖果数)。
算法1
(数学) $O(n)$
题解:我们可以使用暴力的做法,但是我们可以使用数学公式来优化这一点。首先我们定义我们最多能够完整的给n
个小朋友发$k$轮,这里指的是每一轮每一个小朋友都获得了当前轮次理应获得的糖果。
那么这$k$轮中每一轮所有小朋友应该总共发了:$\frac{n(n+1)}{2},\frac{n(n+1)}{2}+n^2,…,\frac{n(n+1)}{2} + (k-1)n^2$
这是一个首项为$\frac{n(n+1)}{2}$,公差为$n^2$的等差数列,因此如果能够完整的发$k$轮,我们应当有:
$$
\frac{(\frac{n(n+1)}{2} + \frac{n(n+1)}{2} + (k - 1)n^2)k}{2} \leq candies$$
$$n^2k^2+nk-2candies \leq0$$
$$k = (int) \frac{-n + \sqrt{n^2 + 8n^2candies}}{2n^2}
$$
那么对于第$i$个小朋友在这$k$轮中每一轮发了$i + 1,i + 1 + n,…,i + 1+(k -1)n$个糖果,因此每个小朋友在前$k$轮中应该发了
$$
\frac{i + 1 + i + 1 + (k -1)n}{2}
$$
对于剩下的糖果我们只需要从前往后依次从$(k-1)n+1$开始递增分配即可。
时间复杂度$O(n)$
vector<int> distributeCandies(int candies, int n) {
int k = (sqrt(n * n + 8ll * candies * n * n) - n) / (2 * n * n);
vector<int> res(n,0);
if(k > 0)
{
for(int i = 0 ; i < n ; i ++)
{
int cur = ((i + 1) + (k - 1) * n + i + 1) * k / 2;
res[i] = cur;
candies -= cur;
}
}
int start = k * n + 1;
if(candies > 0)
{
for(int i = 0 ; candies > 0 ; i ++)
{
int cur = min(candies,start);
res[i] += cur;
candies -= cur;
start ++;
}
}
return res;
}