class Solution {
public:
vector<int> distributeCandies(int candies, int num_people) {
}
};
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原站题解
rust 解法, 执行用时: 0 ms, 内存消耗: 2.2 MB, 提交时间: 2024-06-03 09:09:18
impl Solution {
pub fn distribute_candies(mut candies: i32, n: i32) -> Vec<i32> {
let n = n as usize;
let mut ans = vec![0; n];
let mut i = 1;
while candies > 0 {
ans[(i - 1) as usize % n] += i.min(candies);
candies -= i;
i += 1;
}
ans
}
// 数学
pub fn distribute_candies2(candies: i32, n: i32) -> Vec<i32> {
let m = (((8.0 * candies as f64 + 1.0).sqrt() - 1.0) / 2.0) as i32;
let k = m / n;
let extra = m % n;
let mut ans = (0..n).map(|i| {
let k = if i < extra { k + 1 } else { k };
k * (k - 1) / 2 * n + k * (i + 1)
}).collect::<Vec<_>>();
ans[extra as usize] += candies - m * (m + 1) / 2;
ans
}
}
javascript 解法, 执行用时: 52 ms, 内存消耗: 49.3 MB, 提交时间: 2024-06-03 09:08:18
/**
* @param {number} candies
* @param {number} num_people
* @return {number[]}
*/
var distributeCandies = function(candies, n) {
const m = Math.floor((Math.sqrt(8 * candies + 1) - 1) / 2);
const k = Math.floor(m / n);
const extra = m % n;
const ans = Array(n).fill(0);
for (let i = 0; i < n; i++) {
ans[i] = k * (k - 1) / 2 * n + k * (i + 1) + (i < extra ? k * n + i + 1 : 0);
}
ans[extra] += candies - m * (m + 1) / 2;
return ans;
};
// 模拟
var distributeCandies2 = function(candies, n) {
const ans = Array(n).fill(0);
for (let i = 1; candies > 0; i++) {
ans[(i - 1) % n] += Math.min(i, candies);
candies -= i;
}
return ans;
};
java 解法, 执行用时: 1 ms, 内存消耗: 40.2 MB, 提交时间: 2024-06-03 09:07:40
public class Solution {
public int[] distributeCandies(int candies, int n) {
int[] ans = new int[n];
for (int i = 1; candies > 0; i++) {
ans[(i - 1) % n] += Math.min(i, candies);
candies -= i;
}
return ans;
}
// 数学
public int[] distributeCandies2(int candies, int n) {
int m = (int) ((Math.sqrt(8.0 * candies + 1) - 1) / 2);
int k = m / n;
int extra = m % n;
int[] ans = new int[n];
for (int i = 0; i < n; i++) {
ans[i] = k * (k - 1) / 2 * n + k * (i + 1) + (i < extra ? k * n + i + 1 : 0);
}
ans[extra] += candies - m * (m + 1) / 2;
return ans;
}
}
cpp 解法, 执行用时: 0 ms, 内存消耗: 7.4 MB, 提交时间: 2024-06-03 09:07:09
class Solution {
public:
vector<int> distributeCandies(int candies, int n) {
int m = (sqrt(8.0 * candies + 1) - 1) / 2;
int k = m / n, extra = m % n;
vector<int> ans(n);
for (int i = 0; i < n; i++) {
ans[i] = k * (k - 1) / 2 * n + k * (i + 1) + (i < extra ? k * n + i + 1 : 0);
}
ans[extra] += candies - m * (m + 1) / 2;
return ans;
}
// 模拟
vector<int> distributeCandies2(int candies, int n) {
vector<int> ans(n);
for (int i = 1; candies > 0; i++) {
ans[(i - 1) % n] += min(i, candies);
candies -= i;
}
return ans;
}
};
python3 解法, 执行用时: 43 ms, 内存消耗: 16.6 MB, 提交时间: 2024-06-03 09:06:34
class Solution:
def distributeCandies(self, candies: int, n: int) -> List[int]:
ans = [0] * n
i = 1
while candies > 0:
ans[(i - 1) % n] += min(i, candies)
candies -= i
i += 1
return ans
# 数学
def distributeCandies2(self, candies: int, n: int) -> List[int]:
m = int((sqrt(8 * candies + 1) - 1) / 2)
k, extra = divmod(m, n)
ans = [k * (k - 1) // 2 * n + k * (i + 1) +
(k * n + i + 1 if i < extra else 0)
for i in range(n)]
ans[extra] += candies - m * (m + 1) // 2
return ans
golang 解法, 执行用时: 1 ms, 内存消耗: 2.1 MB, 提交时间: 2024-06-03 09:05:54
// 数学
func distributeCandies(candies, n int) []int {
m := int((math.Sqrt(float64(8*candies+1)) - 1) / 2)
k, extra := m/n, m%n
ans := make([]int, n)
for i := range ans {
k := k
if i < extra {
k++
}
ans[i] = k*(k-1)/2*n + k*(i+1)
}
ans[extra] += candies - m*(m+1)/2
return ans
}
// 模拟
func distributeCandies2(candies, n int) []int {
ans := make([]int, n)
for i := 1; candies > 0; i++ {
ans[(i-1)%n] += min(i, candies)
candies -= i
}
return ans
}
golang 解法, 执行用时: 0 ms, 内存消耗: 2 MB, 提交时间: 2021-07-01 14:56:34
func distributeCandies(candies int, num_people int) []int {
ans := make([]int, num_people)
t := 0
j := 0
for candies > 0 {
for i := 0; i < num_people; i++ {
t = min(i+1 + j * num_people, candies)
ans[i] += t
candies -= t
}
j++
}
return ans
}
func min(x, y int) int {
if x > y {
return y
}
return x
}