放置盒子

发表于 更新于 分类于

    1739. 放置盒子

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

    • 你可以把盒子放在地板上的任何地方。

    • 如果盒子 x 需要放置在盒子 y 的顶部，那么盒子 y 竖直的四个侧面都 必须 与另一个盒子或墙相邻。

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

    示例 1：

    ```txt

    输入：n = 3

    输出：3

    解释：上图是 3 个盒子的摆放位置。

    这些盒子放在房间的一角，对应左侧位置。

    ```

    示例 2：

    ```txt

    输入：n = 4

    输出：3

    解释：上图是 3 个盒子的摆放位置。

    这些盒子放在房间的一角，对应左侧位置。

    ```

    示例 3：

    ```txt

    输入：n = 10

    输出：6

    解释：上图是 10 个盒子的摆放位置。

    这些盒子放在房间的一角，对应后方位置。

    ```

    提示：

    • 1 <= n <= 10^9

题目

1739. 放置盒子

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

  • 1 <= n <= 10^9

题解

方法一：

思路

个人思路二分套二分。
用f(x)表示底层放x个盒子最多能堆积的盒子总数。
那么我们只需要找到第一个x使得f(x)大于等于n, 那么x就是答案。
对于f(x)的计算
找到了规律：当有x个盒子在底层，上一层最多有x-r个，其中r是第一个使得r * (r+1) / 2 >= x的数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    using ll = long long;
    unordered_map<ll, ll> mp;
    ll max_box(ll x) {
        if (mp.count(x)) return mp[x];
        if (x <= 1) return x;
        ll l = 1, r = x+5;
        while (l<r) {
            ll m = l+r>>1;
            if (m*(m+1)>=2*x) {
                r = m;
            } else l = m+1;
        }
        return mp[x] = x + max_box(x-r);
    }
    int minimumBoxes(int n) {
        ll l = 1, r = n;
        while (l<r) {
            ll m = l+r>>1;
            if (max_box(m)>=n) {
                r = m;
            } else l = m+1;
        }
        return r;
    }
};