1739. 放置盒子
有一个立方体房间，其长度、宽度和高度都等于 n 个单位。请你在房间里放置 n 个盒子，每个盒子都是一个单位边长的立方体。放置规则如下：
x 需要放置在盒子 y 的顶部，那么盒子 y 竖直的四个侧面都 必须 与另一个盒子或墙相邻。给你一个整数 n ，返回接触地面的盒子的 最少 可能数量。
示例 1：
输入：n = 3 输出：3 解释：上图是 3 个盒子的摆放位置。 这些盒子放在房间的一角，对应左侧位置。
示例 2：
输入：n = 4 输出：3 解释：上图是 3 个盒子的摆放位置。 这些盒子放在房间的一角，对应左侧位置。
示例 3：
输入：n = 10 输出：6 解释：上图是 10 个盒子的摆放位置。 这些盒子放在房间的一角，对应后方位置。
提示：
1 <= n <= 109原站题解
python3 解法, 执行用时: 40 ms, 内存消耗: 14.9 MB, 提交时间: 2022-12-25 11:40:28
class Solution:
def minimumBoxes(self, n: int) -> int:
x = int((6 * n) ** (1 / 3))
ans = x * (x + 1) // 2
max_n = x * (x + 1) * (x + 2) // 6
if max_n > n:
max_n -= ans
ans -= x
return ans + ceil((-1 + (1 + 8 * (n - max_n)) ** 0.5) / 2)
java 解法, 执行用时: 0 ms, 内存消耗: 38.7 MB, 提交时间: 2022-12-25 11:39:38
class Solution {
public int minimumBoxes(int n) {
int x = (int) Math.cbrt(6L * n);
int ans = x * (x + 1) / 2;
int maxN = (int) ((long) x * (x + 1) * (x + 2) / 6);
if (maxN > n) {
maxN -= ans;
ans -= x;
}
return ans + (int) Math.ceil((-1 + Math.sqrt(1 + 8 * (n - maxN))) / 2);
}
}
cpp 解法, 执行用时: 0 ms, 内存消耗: 6 MB, 提交时间: 2022-12-25 11:39:26
class Solution {
public:
int minimumBoxes(int n) {
int x = cbrt(6L * n);
int ans = x * (x + 1) / 2;
int max_n = (long) x * (x + 1) * (x + 2) / 6;
if (max_n > n) {
max_n -= ans;
ans -= x;
}
return ans + ceil((-1 + sqrt(1 + 8 * (n - max_n))) / 2);
}
};
golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2022-12-25 11:39:11
func minimumBoxes(n int) int {
x := int(math.Cbrt(float64(6 * n)))
ans := x * (x + 1) / 2
maxN := x * (x + 1) * (x + 2) / 6
if maxN > n {
maxN -= ans
ans -= x
}
return ans + int(math.Ceil((-1+math.Sqrt(float64(1+8*(n-maxN))))/2))
}
golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2022-12-25 11:38:49
func minimumBoxes(n int) (ans int) {
maxN := 0
for i := 1; maxN+ans+i <= n; i++ {
ans += i
maxN += ans
}
for j := 1; maxN < n; j++ {
ans++
maxN += j
}
return
}
cpp 解法, 执行用时: 0 ms, 内存消耗: 5.8 MB, 提交时间: 2022-12-25 11:38:34
class Solution {
public:
int minimumBoxes(int n) {
int ans = 0, max_n = 0;
for (int i = 1; max_n + ans + i <= n; ++i) {
ans += i;
max_n += ans;
}
for (int j = 1; max_n < n; ++j) {
++ans;
max_n += j;
}
return ans;
}
};
java 解法, 执行用时: 1 ms, 内存消耗: 38.5 MB, 提交时间: 2022-12-25 11:38:15
class Solution {
public int minimumBoxes(int n) {
int ans = 0, maxN = 0;
for (int i = 1; maxN + ans + i <= n; ++i) {
ans += i;
maxN += ans;
}
for (int j = 1; maxN < n; ++j) {
++ans;
maxN += j;
}
return ans;
}
}
python3 解法, 执行用时: 36 ms, 内存消耗: 14.9 MB, 提交时间: 2022-12-25 11:37:51
class Solution:
def minimumBoxes(self, n: int) -> int:
ans = max_n = 0
i = j = 1
while max_n + ans + i <= n:
ans += i
max_n += ans
i += 1
while max_n < n:
ans += 1
max_n += j
j += 1
return ans