Сложность: 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:
def distributeCandies(self, candies: int, num_people: int) -> List[int]:
n = num_people
p = int((2 * candies + 0.25)**0.5 - 0.5)
remaining = int(candies - (p + 1) * p * 0.5)
rows, cols = p // n, p % n
d = [0] * n
for i in range(n):
d[i] = (i + 1) * rows + int(rows * (rows - 1) * 0.5) * n
if i < cols:
d[i] += i + 1 + rows * n
d[cols] += remaining
return d
Ставь 👍 и забирай 📚 Базу знаний