题目描述
有一个立方体房间,其长度、宽度和高度都等于 n
个单位。请你在房间里放置 n
个盒子,每个盒子都是一个单位边长的立方体。放置规则如下:
- 你可以把盒子放在地板上的任何地方。
- 如果盒子
x
需要放置在盒子y
的顶部,那么盒子y
竖直的四个侧面都 必须 与另一个盒子或墙相邻。
给定一个整数 n
,返回接触地面的盒子的 最少 可能数量。
样例
输入:n = 3
输出:3
解释:上图是 3 个盒子的摆放位置。
这些盒子放在房间的一角,对应左侧位置。
输入:n = 4
输出:3
解释:上图是 3 个盒子的摆放位置。
这些盒子放在房间的一角,对应左侧位置。
输入:n = 10
输出:6
解释:上图是 10 个盒子的摆放位置。
这些盒子放在房间的一角,对应后方位置。
限制
1 <= n <= 10^9
算法
(二分答案,贪心找规律) $O(\sqrt n \log^2 n)$
- 二分底座的个数。
- 假设底座的个数为
x
个。注意到,底座的最优的放置方式一定是第一行放 1 个,第二行放 2 个,以此类推,第 $t + 1$ 行不足 $t + 1$ 个。 - 得到 $t$ 后,第二层可以放置 $t(t + 1)/2$ 个。计算出第 $t + 1$ 行剩余的个数 $r$。如果 $r$ 大于 0,则第二层可以额外放置 $r - 1$ 个。
- 第三层由第二层按照同样的方式推出。如果放置的总个数大于等于 $n$,则可以下调二分的范围。
时间复杂度
- 二分 $O(\log n)$ 次。
- 二分时,共有最多 $O(\sqrt n)$ 层,每一层需要 $O(\log n)$ 的时间求 $t$。
- 故总时间复杂度为 $O(\sqrt n \log^2 n)$,但实际常数非常小。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
#define LL long long
class Solution {
private:
LL get(LL x) {
LL l = 1, r = x;
while (l < r) {
LL mid = (l + r) >> 1;
if ((mid + 1) * (mid + 2) / 2 > x) r = mid;
else l = mid + 1;
}
return l;
}
bool check(LL x, int n) {
LL tot = x;
while (x >= 3 && tot < n) {
LL t = get(x);
LL r = x - t * (t + 1) / 2;
x = (t - 1) * t / 2;
if (r > 0) x += r - 1;
tot += x;
}
return tot >= n;
}
public:
int minimumBoxes(int n) {
LL l = 1, r = n;
while (l < r) {
LL mid = (l + r) >> 1;
if (check(mid, n)) r = mid;
else l = mid + 1;
}
return l;
}
};