1103、分糖果II
排排坐，分糖果。
我们买了一些糖果 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^91 <= num_people <= 1000
链接：https://leetcode-cn.com/problems/distribute-candies-to-people
题解
1、模拟分配
利用取模运算直接分配。
public class Solution {
public int[] distributeCandies(int candies,int num_people) {
int[] res = new int[num_people];
int count = 0;
while (candies > 0) {
if (candies >= count+1){
res[count%num_people] += count+1;
}else {
res[count % num_people] += candies;
break;
}
candies -= count+1;
}
return res;
}
}
class Solution {
public int[] distributeCandies(int candies, int num_people) {
// 模拟
int[] ans = new int[num_people];
int base = 1;// current candies to give
int index = 0;
while (candies > 0) {
if (candies >= base) {
candies -= base;
ans[index] += base;
} else {
ans[index] += candies;
candies = 0;
}
base++;
index++;
index = index%num_people;
}
return ans;
}
}
2、计算组数，至多循环两次
- 先计算可以分配的组数有多少：
candies个糖果分配给num_people个小朋友。
第i组需要的糖果数量为：
$$
a_i = \frac{n(n+1)}{2} + (i - 1) · n^2
= \frac{(2·i - 1)n^2 + n}{2}
$$
- 然后，将可以完全分配的组数先分配。
假如我们计算了需要分配count次，那么，最后一次算作不完全分配。我们可以对前count-1次进行统一分配，因为相邻的小朋友，固定相差count-1个糖果。
对于第一个小朋友：
第i组分配到的糖果数量为：
$$ a_0 = 1,a_i = 1 + (i - 1)*n，$$
那么第一位同学分配到第i组时，总共的糖果数量为：
$$ S_i = (1 + 1 + (i - 1)·n)*i/2 $$
之后的，同学与前一位同学的糖果数量关系为：
$$ s_i = s_{i - 1} + count - 1; $$
- 处理最后一组的不完全分配。
最后一组（ 第count组 ），第一位同学应该分配的糖果数量为：
$$ a_{count} = 1 + n(count - 1) $$
然后，模拟分配即可。
class Solution {
public int[] distributeCandies(int candies, int num_people) {
int[] res = new int[num_people];
// 第一轮需要的所有的糖果数量
int sum = (1+num_people)*num_people/2;
int count = 1;
// 统计可以分多少组
while (candies >= sum) {
count++;
sum += ((2*count-1)*num_people*num_people + num_people)/2;
}
if (count == 1) { // 只有一组
for (int i = 0;i < num_people;i++) {
if (candies < i) {
res[i] = candies;
break;
}else {
res[i] = i+1;
candies -= i+1;
}
}
} else { // 存在多组
// 计算第一位同学可以获得的 前count - 1组的糖果数量
int first = (1 + (count-2)*num_people + 1)*(count-1)/2;
// 推到出所有同学的糖果数量
for (int i = 0;i < num_people;i++) {
if (i == 0) {
res[i] = first;
} else {
// 第i为同学的糖果数量比前一位同学的多count - 1个
res[i] = res[i-1] + count - 1;
}
candies -= res[i];
}
// 处理最后一行的糖果分配，因为可能分配不全。
// 最后一组分配的
first = 1+num_people*(count-1);
for (int i = 0;i < num_people;i++) {
if (candies >= first) {
res[i] += first;
candies -= first;
first++;
}else {
res[i] += candies;
break;
}
}
}
return res;
}
}
3、先一次性分配到位，再从后往前去除超额的。
不用再分情况分配了。
class Solution {
public int[] distributeCandies(int candies, int num_people) {
int[] res = new int[num_people];
// 第一轮需要的所有的糖果数量
int sum = (1+num_people)*num_people/2;
int count = 1;
// 统计可以分多少组
while (candies >= sum) {
count++;
sum += ((2*count-1)*num_people*num_people + num_people)/2;
}
// 计算第一位同学可以获得的 前count - 1组的糖果数量
int first = (1 + (count-1)*num_people + 1)*(count)/2;
// 推到出所有同学的糖果数量
for (int i = 0;i < num_people;i++) {
if (i == 0) {
res[i] = first;
} else {
// 第i为同学的糖果数量比前一位同学的多count - 1个
res[i] = res[i-1] + count;
}
candies -= res[i];
}
// 说明最后一组超额分配了
if (candies < 0) {
int last = count*num_people;
for (int i = num_people - 1;i >= 0;i--) {
if (candies + last <= 0) {
// 多分配了last个
res[i] -= last;
} else {
// 第一个多分配的同学，多分配了 -candies个
res[i] -= -candies;
break;
}
candies += last;
last--;
}
}
return res;
}
}
4、等差数列求和
求出当前糖果数可以多少人：
$$ S_n = \frac{(n+1)n}{2} $$
找到最后一个小于candies的$S_n$，把candies带进去进行计算即可：
求根公式：
$$ candies = \frac{(n+1)n}{2} $$
$$a=1,b=1,c=-2candies$$
$$
n = \frac{-1+_-\sqrt{1+8candies}}{2}
$$
化简：
$$
p = floor({-\frac{1}{2}+\sqrt{\frac{1}{4}+2*candies}})
$$
剩余没能按照规则发的糖果：
$$
last_candies = candies - \frac{p(p+1)}{2}
$$
可以计算发了多少轮：取商
$$ rows = p / num_people $$
class Solution {
public int[] distributeCandies(int candies, int num_people) {
int n = num_people;
// how many people received complete gifts
int p = (int) (Math.sqrt(2 * candies + 0.25) - 0.5);
int remaining = (int) (candies - (p + 1) * p * 0.5);
int rows = p / n, cols = p % n;
int[] d = new int[n];
for (int i = 0; i < n; ++i) {
// complete rows
d[i] = (i + 1) * rows + (int) (rows * (rows - 1) * 0.5) * n;
// cols in the last row
if (i < cols) {
d[i] += i + 1 + rows * n;
}
}
// remaining candies
d[cols] += remaining;
return d;
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
