1103. Distribute Candies to People

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

这题给了N个糖果，需要分给M个人，按顺序轮流发，第一个人领1个，第二个2个，第N个N个，假设糖果还没发完，则继续，不过需要继续递增，比如第一个人第二轮就是1+N个了。需要求出发完后每个人能领到的糖果数量。

这题我可能想复杂了，首先先计算出能发多少轮，这里可以用等差数列来完成。得到这个之后，我们就能知道最后一轮的分配情况，然后根据发完多少轮，又可以通过等差数列来计算出每个人从第一轮到N轮总共可以获得多少个糖果，最后的和就是解。

class DistributeCandiesToPeople : public Solution {
public:
    void Exec() {
        auto res = distributeCandies(132,7);
    }
    vector<int> distributeCandies(int candies, int num_people) {
        vector<int> res;
        res.resize(num_people, 0);
        int base_round = num_people * (1 + num_people) / 2;

        int round = 0;
        int round_inc = num_people * num_people;
        while (candies > 0) {
            int dist = base_round + round * round_inc;
            if (dist > candies) {
                break;
            }
            candies -= dist;
            round++;
        }

        int index = 0;
        while (candies > 0) {
            int cur = 1 + index + round * num_people;
            if (candies > cur) {
                candies -= cur;
                res[index] = cur;
            } else {
                res[index] = candies;
                candies = 0;
            }
            index++;
        }

        if (round > 0) {
            for (int i = 0; i < num_people; i++) {
                res[i] += round * (i + 1 + i + 1 + (round - 1) * num_people) / 2;
            }
        }

        return res;
    }
};