内容简介:我们用下面的方法给num_people个人分发一些糖果:我们给第一个人1块糖,给第二个人2块糖,以此类推,直到我们给最后一个人n块糖。
本文为LeetCode 1103: Distribute Candies to People 的题解。
题意
我们用下面的方法给num_people个人分发一些糖果:
我们给第一个人1块糖,给第二个人2块糖,以此类推,直到我们给最后一个人n块糖。
然后,我们回到开始,给第一个人n + 1块糖,给第二个人n + 2块糖,以此类推,直到我们给最后一个人2 * n块糖。
这个过程不断重复(当重新走到队首的时候,我们每次比上次多给n个糖果),直到糖果分配结束。最后一个人将收到我们所有剩余的糖果。
返回一个数组(长度为num_people),该数组表示最终每个人得到的糖果数量。
题解
首先我们考虑能完整的分发几轮。
由于分发数量总体上就是从1到n*num_people的等差序列,n符合如下不等式:
\(
\sum_{i=1}^{n*num\_people}i \leq candies \rightarrow n \leq \frac{\sqrt{2*candies+\frac{1}{4}}-\frac{1}{2}}{num\_people}
\)
然后对于剩下的,进行一次分发即可:
import java.util.Arrays;
class Solution {
public int[] distributeCandies(int candies, int num_people) {
int[] result = new int[num_people];
// 能进行完整分配的次数
int completeRound = (int) ((Math.sqrt(2 * candies + 1 / 4.) - 1 / 2.) / num_people);
// 分配
for (int i = 0; i < num_people; i++) {
result[i] = completeRound * (i + 1) + (completeRound - 1) * completeRound * num_people / 2;
}
// 减掉分配过的
candies -= (1 + completeRound * num_people) * completeRound * num_people / 2;
// 开始最后一轮分配
for (int i = 0; i < num_people && candies > 0; i++) {
int giveCandie = completeRound * num_people + i + 1;
if (candies < giveCandie) {
giveCandie = candies;
}
result[i] += giveCandie;
candies -= giveCandie;
}
return result;
}
public static void main(String[] args) {
int[] res = new Solution().distributeCandies(10, 3);
System.out.println(Arrays.toString(res));
// 输出 [5, 2, 3]
}
}
以上所述就是小编给大家介绍的《LeetCode 1103:Distribute Candies to People》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
单元测试之道Java版
David Thomas、Andrew Hunt / 陈伟柱、陶文 / 电子工业 / 2005-1 / 25.00元
程序员修炼三部曲丛书包含了四本书,介绍了每个注重实效的程序员和成功团队所必备的一些工具。 注重实效的程序员都会利用反馈来指导开发,并驱动个人的开发流程。编码的时候,最有用的反馈来自于“单元测试”。 为了测试一座桥梁,不会只在晴朗的天气,开一辆汽车从桥中间穿过,就认为已经完成了对桥梁的测试。然而许多程序员却正在使用这种测试方法——把这种一次顺利通过称为“测试”。事实上,注重实效的程序员应......一起来看看 《单元测试之道Java版》 这本书的介绍吧!