放置盒子

有一个立方体房间，其长度、宽度和高度都等于 n 个单位。请你在房间里放置 n 个盒子，每个盒子都是一个单位边长的立方体。放置规则如下：

你可以把盒子放在地板上的任何地方。
如果盒子 x 需要放置在盒子 y 的顶部，那么盒子 y 竖直的四个侧面都 必须 与另一个盒子或墙相邻。
给你一个整数 n ，返回接触地面的盒子的 最少 可能数量。

示例 1：
输入：n = 3
输出：3
解释：上图是 3 个盒子的摆放位置。
这些盒子放在房间的一角，对应左侧位置。

示例 2：
输入：n = 4
输出：3
解释：上图是 3 个盒子的摆放位置。
这些盒子放在房间的一角，对应左侧位置。

示例 3：
输入：n = 10
输出：6
解释：上图是 10 个盒子的摆放位置。
这些盒子放在房间的一角，对应后方位置。
 
提示：

1 <= n <= 109

作者：字节校园
链接：https://leetcode-cn.com/leetbook/read/bytedance-c01/eikfoc/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {
    public int minimumBoxes(int n) {

        // 先算饱和时盒子接触地面的数量，因为在饱和之前，上一层每新增1个下一层面要增加2个
        // 饱和后，最下层先增加一个，随后下一层每增加一个，上一层可以增加一个

        int level = 1;// 层数
        int boxNum = 0;// 盒子的数量

        while (boxNum + ((1 + level) * level / 2) <= n) {
            // 从上到下每一层的盒子的数量num=(i+1)*i/2
            boxNum += (1 + level) * level / 2;
            level++;
        }
        // 多加了一个减回来
        level--;

        // 饱和时第一层的数量
        int area = (1 + level) * level / 2;
        // 除第一层外每层增加的数量
        int now = 0;
        while (boxNum < n) {
            area += 1;
            boxNum += now + 1;
            now++;
        }

        return area;
    }
}

参考文献

【放置盒子】解题时的思路+详细说明（O(logN)时间复杂度）作者：长行

赏

谢谢你请我吃糖果

微信