LeetCode 1103:Distribute Candies to People

栏目: 编程工具 · 发布时间: 6年前

内容简介:我们用下面的方法给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》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Rails 5敏捷开发

Rails 5敏捷开发

[美] Sam Ruby、[美] Dave Thomas、[美] David Heinemeier Hansson / 安道、叶炜、大疆Ruby技术团队 / 华中科技大学出版社 / 2017-12-30 / 115.00

本书以讲解“购书网站”案例为主线,逐步介绍Rails的内置功能。全书分为3部分,第一部分介绍Rails的安装、应用程序验证、Rails框架的体系结构,以及Ruby语言知识;第二部分用迭代方式构建应用程序,然后依据敏捷开发模式开展测试,最后用Capistrano完成部署;第三部分补充日常实用的开发知识。本书既有直观的示例,又有深入的分析,同时涵盖了Web开发各方面的知识,堪称一部内容全面而又深入浅出......一起来看看 《Rails 5敏捷开发》 这本书的介绍吧!

CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具