【LetMeFly】1739.放置盒子

力扣题目链接：https://leetcode.cn/problems/building-boxes/

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

• 你可以把盒子放在地板上的任何地方。
• 如果盒子 x 需要放置在盒子 y 的顶部，那么盒子 y 竖直的四个侧面都 必须 与另一个盒子或墙相邻。

给你一个整数 n ，返回接触地面的盒子的 最少 可能数量。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 1 <= n <= 109

方法一：思维

具体的放置方法可以参考灵神@灵茶山艾府的动态图

首先，就是在放置总量$total$未达到$n$时，不断地将某层放满。（第一层1个，第二层3个，第三层6个，第四层10个）

这时候，盒子总量已经等于或者超过$n$了。我们将盒子状态返回“最后一层”放完之前的状态，然后，一个一个地往最下面一层放盒子。

第$i$次往最下面一层放盒子，盒子总量能增加$i$个。

接着枚举直到总量大于等于$n$即可。

• 时间复杂度：不好计算，官解说：${}^3\sqrt{n}$
• 空间复杂度$O(1)$

AC代码

C++

typedef long long ll;
class Solution {
public:int minimumBoxes(ll n) {ll bottom = 1, nextAdd = 2;ll total = 1;ll lastBottom, lastTotal;while (total <= n) {  // 最下面一层“放满”，上面也放满lastBottom = bottom, lastTotal = total;bottom += nextAdd, nextAdd++;total += bottom;}total = lastTotal, bottom = lastBottom;ll ans = bottom;for (int i = 1; total < n; i++) {ans++;total += i;}return ans;}
};

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/128436934