第 225 场周赛 5664. 放置盒子

最后一题没时间做，好菜好气。rank 567

Desciption

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

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

输入: n = 4
输出: 3

输入: n = 10
输出: 6

Solution

  1. 看到“最多”，“最少”，“最大”，“最小”的字眼，优先想的是 二分答案
  2. 考虑二分答案，即知道了最底层的数量，怎么看它最多能放多少个盒子呢
  3. 找规律：
    1. 假设盒子足够多，最优的放置是 顶层肯定是放 1 个，然后第二层放 3 个，接着依次是 6， 10， 15……，可以看到是 1 + 2 + 3 + 4 + 5 这样的规律
    2. 假设底层放了 10 个，上面一层只能放 6 个。接着如果最底层多了 x (x <= 5) 个，上面一层就可以多放 x - 1 个
  4. 编码：我们知道了最底层的数量，参照第三点的规律，可以计算倒数第二层的数量，然后可以接着计算倒数第三层的数量，从而知道它最多能放多少个盒子

Code

    public long check(long x) {
        long res = 0;
        while (x > 0) {
            res += x;
            long L = 1, R = x;
            while (L < R) {
                long mid = (L + R) >> 1;
                if ((1 + mid) * mid / 2 >= x) {
                    R = mid;
                } else {
                    L = mid + 1;
                }
            }
            if ((1 + L) * L / 2 >= x) {
                L--;
            }
            if ((1 + L) * L / 2 + L + 1 > x) {
                L--;
            }
            //System.out.println("L = " + L);
            long y = (1 + L) * L / 2;
            // 对应3.2，得到剩下多了的盒子数量
            long left = x - y - L - 1;
            // 得到上一层的数量，传给x
            x = y + (left >= 2 ? left - 1 : 0);
            //System.out.println("x = " + x);
        }
        return res;
    }
    public int minimumBoxes(int n) {
        int L = 1, R = n;
        while (L < R) {
            int mid = (L + R) >> 1;
            if (check(mid) >= n) {
                R = mid;
            } else {
                L = mid + 1;
            }
        }
        return L;
    }