# 1103.Distribute Candies to People

**1103.Distribute Candies to People**

难度:Easy

> 排排坐，分糖果。 我们买了一些糖果 candies，打算把它们分给排好队的 `n = num_people` 个小朋友。 给第一个小朋友 1 颗糖果，第二个小朋友 2 颗，依此类推，直到给最后一个小朋友 n 颗糖果。 然后，我们再回到队伍的起点，给第一个小朋友 n + 1 颗糖果，第二个小朋友 n + 2 颗，依此类推，直到给最后一个小朋友 2 \* n 颗糖果。 重复上述过程（每次都比上一次多给出一颗糖果，当到达队伍终点后再次从队伍起点开始），直到我们分完所有的糖果。注意，就算我们手中的剩下糖果数不够（不比前一次发出的糖果多），这些糖果也会全部发给当前的小朋友。 返回一个长度为 `num_people`、元素之和为 candies 的数组，以表示糖果的最终分发情况（即 ans\[i] 表示第 i 个小朋友分到的糖果数）。

```
示例 1：

输入：candies = 7, num_people = 4
输出：[1,2,3,1]
解释：
第一次，ans[0] += 1，数组变为 [1,0,0,0]。
第二次，ans[1] += 2，数组变为 [1,2,0,0]。
第三次，ans[2] += 3，数组变为 [1,2,3,0]。
第四次，ans[3] += 1（因为此时只剩下 1 颗糖果），最终数组变为 [1,2,3,1]。
示例 2：

输入：candies = 10, num_people = 3
输出：[5,2,3]
解释：
第一次，ans[0] += 1，数组变为 [1,0,0]。
第二次，ans[1] += 2，数组变为 [1,2,0]。
第三次，ans[2] += 3，数组变为 [1,2,3]。
第四次，ans[0] += 4，最终数组变为 [5,2,3]。
 

提示：

1 <= candies <= 10^9
1 <= num_people <= 1000
```

每轮糖果呈等差数列，设第一轮等差数列和为S,接下来一轮每个人多n颗糖果，总数为`S+n*n`。每经过一轮，总糖果数都多了`n*n`，以此类推，这又是一个等差数列。\
因此初步想法是，对于给定的糖果数，假设已经经过了M次完整的循环，那么可以根据总糖果数求出M。剩下的糖果数，从M+1次开始分糖果，当满足当前people需要的所有糖果时，分其所需要的；当不满足时，全给他，终止循环。\
代码如下： 求M的公式最后可以化简为一个一元二次方程，其中a,b如代码中所示，c就是`-candies`。\
`sum`表示前M次完整循环，一共用了多少糖果。\
接下来一个循环，求出前M次分糖果，每个人分得的堂果蔬，又是一个等差数列求和。\
r表示残留糖果数。\
最后一个for循环，从r里分，tmp表示当前people需要的糖果数，当剩余糖果数充足时，分tmp，不充足时，全给。

```
class Solution {
public:
    vector<int> distributeCandies(int candies, int num_people) {
        double a=num_people*num_people/2.0;
        double b=num_people/2.0;
        int count=(sqrt(b*b+4*a*candies) -b)/(2.0*a);
        vector<int >res(num_people);
        int sum=(count-1)*count/2*num_people*num_people +count*(num_people+1)*num_people/2;
            for(size_t i=0; i<num_people;i++)
            res[i]+=num_people*(count-1)*count/2 + count*(i+1);
        int r=candies-sum;
        for(size_t i=0;i<num_people;i++)
        {
         int tmp=count*num_people+i+1;
            if(tmp<r)
            {res[i]+=tmp;
             r-=tmp;
        }
            else
            {res[i]+=r;
            break;}
        }

        
        cout<<"a: "<< a << "b: " << b<< "count: "<<count<<"sum: "<<sum<<endl;
        return res;
    }
};
```

> 执行用时 :4ms, 在所有 C++ 提交中击败了91.38%的用户\
> 内存消耗 :8.6MB, 在所有 C++ 提交中击败了100%的用户


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://dfine.gitbook.io/leetcode/1103.distribute_candies_to_people.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.