Сложность: easy
Мы распределяем некоторое количество конфет ряду из n = num_people человек следующим образом:
Сначала даем 1 конфету первому человеку, 2 конфеты второму человеку и так далее, пока не дадим n конфет последнему человеку.
Затем мы возвращаемся к началу ряда, давая n + 1 конфету первому человеку, n + 2 конфеты второму человеку и так далее, пока не дадим 2 * n конфет последнему человеку.
Этот процесс повторяется (мы каждый раз даем на одну конфету больше и возвращаемся к началу ряда после достижения конца), пока у нас не закончатся конфеты. Последний человек получит все оставшиеся конфеты (не обязательно на одну больше, чем в предыдущий раз).
Верните массив (длиной num_people и суммой candies), который представляет собой окончательное распределение конфет.
Пример:
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].
👨💻 Алгоритм:
1⃣Вычислите количество людей, получивших полные подарки, и оставшиеся конфеты:
p = floor(sqrt(2C+0.25)-0.5)
remainig = C - p(p+1)/2
2⃣Вычислите количество полных циклов и распределите конфеты:
rows = p // n
d[i]= i*rows + n*rows*(rows-1)/2
3⃣Добавьте конфеты за дополнительный неполный цикл и оставшиеся конфеты:
d[i]+=i+n⋅rows для первых p%n людей
d[p%n]+=remaining
Верните распределение конфет d
😎 Решение:
class Solution {
public int[] distributeCandies(int candies, int num_people) {
int n = num_people;
int p = (int) (Math.sqrt(2 * candies + 0.25) - 0.5);
int remaining = candies - (p + 1) * p / 2;
int rows = p / n;
int cols = p % n;
int[] d = new int[n];
for (int i = 0; i < n; i++) {
d[i] = (i + 1) * rows + (rows * (rows - 1) / 2) * n;
if (i < cols) {
d[i] += i + 1 + rows * n;
}
}
d[cols] += remaining
return d;
}
}Ставь 👍 и забирай 📚 Базу знаний