LeetCode刷题： 【1103】分糖果 II（等差数列）

LeetCode刷题： 【1103】分糖果 II（等差数列）

1. 题目

排排坐，分糖果。

我们买了一些糖果 candies，打算把它们分给排好队的 n = num_people 个小朋友。

给第一个小朋友 1 颗糖果，第二个小朋友 2 颗，依此类推，直到给最后一个小朋友 n 颗糖果。

然后，我们再回到队伍的起点，给第一个小朋友 n + 1 颗糖果，第二个小朋友 n + 2 颗，依此类推，直到给最后一个小朋友 2 * n 颗糖果。

重复上述过程（每次都比上一次多给出一颗糖果，当到达队伍终点后再次从队伍起点开始），直到我们分完所有的糖果。注意，就算我们手中的剩下糖果数不够（不比前一次发出的糖果多），这些糖果也会全部发给当前的小朋友。

返回一个长度为 num_people、元素之和为 candies 的数组，以表示糖果的最终分发情况（即 ans[i] 表示第 i 个小朋友分到的糖果数）。

来源：力扣（LeetCode）
链接：
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 思路

思路一：最简单当然是暴力法了，直接模拟过程就行，不加赘述
思路二：数学(话说等差数列是初中还是高中数学来着。。。)

1. candies按*规则*最多可以发给num = MAX{n|n*(n+1)<=2*candies}个同学，第num+1个同学得到剩余糖果;
2. 每轮长度为num_people, 能得到 line = num/num_people行，第line+1行只有rest = num%num_people个.
3. 每个人每轮获得的糖果是个等差数列，第一轮的元素为首项，公差为num_people，项数为n = line + (i > rest ? 0 : 1).
4. 第i个同学获得的糖果总数为第i列的前 n 项和;
5. 最后一个同学获得剩余的糖果ans[rest] += candies - num*(num+1)/2.

3. 代码

class Solution {
public:vector<int> distributeCandies(int candies, int num_people) {int num = 0;vector<int> ans(num_people, 0);while(num*(num+1)<=2*candies) num++; // 可以按规则分(num - 1)次num--;int line = num/num_people;int rest = num%num_people;int i = 1;for(; i <= rest; i++){//分到糖果数目为：（首项+尾项）*项数/2ans[i - 1] = (i + i + line*num_people) * (line + 1) / 2;  }for(; i <= num_people; i++){//分到糖果数目为：（首项+尾项）*项数/2ans[i - 1] = (i + i + (line - 1)*num_people) * line / 2; }//将最后剩余的糖果分给最后一个人ans[rest] += candies - num*(num+1)/2 ;return ans;}
};

4. 时间复杂度

O(n) 其中n为人数