題目地址
https://leetcode-cn.com/problems/distribute-candies-to-people/
題目描述
排排坐僚焦，分糖果。
我們買了一些糖果 candies立肘，打算把它們分給排好隊的 n = num_people 個小朋友。
給第一個小朋友 1 顆糖果茧痒，第二個小朋友 2 顆融蹂，依此類推，直到給最后一個小朋友 n 顆糖果区拳。
然后意乓，我們再回到隊伍的起點，給第一個小朋友 n + 1 顆糖果，第二個小朋友 n + 2 顆业汰，依此類推样漆，直到給最后一個小朋友 2 * n 顆糖果。
重復(fù)上述過程（每次都比上一次多給出一顆糖果放祟，當(dāng)?shù)竭_隊伍終點后再次從隊伍起點開始）跪妥，直到我們分完所有的糖果。注意眉撵，就算我們手中的剩下糖果數(shù)不夠（不比前一次發(fā)出的糖果多）纽疟，這些糖果也會全部發(fā)給當(dāng)前的小朋友。
返回一個長度為 num_people污朽、元素之和為 candies 的數(shù)組，以表示糖果的最終分發(fā)情況（即 ans[i] 表示第 i 個小朋友分到的糖果數(shù)）矾睦。
示例 1：
輸入：candies = 7, num_people = 4
輸出：[1,2,3,1]
解釋：
第一次顷锰，ans[0] += 1，數(shù)組變?yōu)?[1,0,0,0]官紫。
第二次束世，ans[1] += 2，數(shù)組變?yōu)?[1,2,0,0]毁涉。
第三次贫堰，ans[2] += 3，數(shù)組變?yōu)?[1,2,3,0]其屏。
第四次偎行，ans[3] += 1（因為此時只剩下 1 顆糖果），最終數(shù)組變?yōu)?[1,2,3,1]蛤袒。
示例 2：
輸入：candies = 10, num_people = 3
輸出：[5,2,3]
解釋：
第一次妙真，ans[0] += 1，數(shù)組變?yōu)?[1,0,0]癌椿。
第二次菱阵，ans[1] += 2，數(shù)組變?yōu)?[1,2,0]晴及。
第三次，ans[2] += 3琳钉，數(shù)組變?yōu)?[1,2,3]。
第四次啦桌，ans[0] += 4及皂，最終數(shù)組變?yōu)?[5,2,3]。
提示：
1 <= candies <= 10^9
1 <= num_people <= 1000
思路
- 模擬分糖果的過程板驳。
- 計算每個孩子要分的次數(shù)碍拆，提前全部分好感混，最后一次的時候可能不夠，所以最后減去多分的糖果就行弧满。
PS :
等差數(shù)列求和公式：項數(shù) * (首項 + 末項) / 2谱秽；
等差數(shù)列第i項值：首項 + （項數(shù) - 1）* 差值洽蛀；
題解
class Solution {
/**
* 執(zhí)行用時： 0 ms , 在所有 Java 提交中擊敗了 100.00% 的用戶
* 內(nèi)存消耗： 36.3 MB , 在所有 Java 提交中擊敗了 21.35%的用戶
*/
public int[] distributeCandies(int candies, int num_people) {
int[] result = new int[num_people];
int max = 1;
// 一直分下去摹迷，不管孩子個數(shù)疟赊，看能分多少個
while (max * (max + 1) <= 2 * candies) {
max++;
}
int all = max * (1 + max) / 2;
for (int i=0; i< num_people; i++) {
int times = max / num_people; // 前整幾輪分的次數(shù)
times += (max % num_people) > i ? 1 : 0; // 最后一輪分的次數(shù)
result[i] = times * (i + 1 + i+1 + (times - 1) * num_people) / 2; // 等差數(shù)列求和公式
}
result[(max - 1) % num_people] -= all - candies; // 最后可能不夠，需要減去
return result;
}
/**
* 執(zhí)行用時： 1 ms , 在所有 Java 提交中擊敗了 89.32% 的用戶
* 內(nèi)存消耗： 36.2 MB , 在所有 Java 提交中擊敗了 52.37% 的用戶
*/
public int[] distributeCandiesV0(int candies, int num_people) {
int[] result = new int[num_people];
int index = 0;
int cand = 1;
while (candies > 0) {
if (cand > candies) {
result[index] += candies;
break;
}
result[index] += cand;
candies -= cand;
index++;
cand++;
if (index >= num_people) {
index = 0;
}
}
return result;
}
}
