leetcode周赛最后一题，放置盒子

那看来我以前比赛排名十来名的时候你没有参加：）

先凡尔赛一下：[手动狗头]

==========

其实这个问题意义不大，我敢 100% 肯定面试不会有这个问题。即使有，这个问题能否做出来也绝不占决定性因素。所以在上面的截图中，我说 lc 周赛现在的问题有些偏了。

整体，这个问题的思路就是，再放了底面的盒子以后，要尽量多的往上面累盒子，才能做到最下面的盒子尽量少。所以关键就是，底面每放一个盒子，上面可以放多少盒子？

我的代码其实复杂了。不过下面根据我的代码作讲解：

代码中，res 对应底面有多少盒子；total 对应一共有多少盒子。total >= n，就可以停止了。

以最后一个用例为例。在这个基础上，下面怎么放？

下面首先必须放两个盒子，才能在上面多放一个盒子。这一共是三个盒子，对应下图中蓝色的部分，我的代码中的 // 1

之后，我们只需要在底面再放一个盒子，就能一共放 3 个盒子了。对应下图中红色的部分。

之后，我们只需要在底面再放一个盒子，就能一共放 4 个盒子了。对应下图中绿色的部分。

所以这是一个等差数列，对应我的代码的 // 2 部分。

class Solution {
public:
    int minimumBoxes(int n) {
        
        if(n == 1) return 1;
        
        int total = 1, res = 1;
        for(int h = 2; h <= n; h ++){
            
            if(total + 1 == n){ res ++; break;}
            
            // 1 最初的那三个
            total += 3, res += 2;
            if(total >= n) break;
            
            // 2 哦后面是等差数列
            for(int x = 3; x <= h; x ++){
                total += x, res ++;
                if(total >= n) break;
            }
            if(total >= n) break;
        }
        return res;
    }
};

在这个基础上，继续放，就是 3 + （3 + 4 + 5）；

再放就是 3 + （3 + 4 + 5 + 6）；

随着高度增加，以此类推。

这里我说我的代码写复杂了，是因为第一部分的 3，可以拆解成 1 + 2，所以，内重循环就是一个从 1 到 h 的等差数列求和，就好了。比赛的时候想歪了，所以前面还有特殊的处理，其实没必要。

代码这样就可以：

class Solution {
public:
    int minimumBoxes(int n) {
        
        int total = 0, res = 0;
        for(int h = 1; h <= n && total < n; h ++){
            for(int x = 1; x <= h && total < n; x ++)
                total += x, res ++;
        }
        return res;
    }
};

==========

这个代码还可以进一步优化。

比如内重循环找让 total >= n 的 x，显然可以使用二分搜索，因为 total 随着 x 单调递增；

进一步，因为内重循环就是一个等差数列求和，所以是一个关于 h 的二次函数，可以使用数学方法直接求出 x

进一步，因为我们可以列出内重循环的式子，而外重循环又是内重循环 h 逐渐增加，所以从外重循环的角度看，整体也是一个数列（和完全平方相关的一个数列），整体都可以使用数学的方式求解。

比赛的时候先基本实现了一下，发现过了，就懒得优化了。

关键还是，这个问题太不典型了，意义没有那么大，没必要花那么多时间。

P.S. 这个问题更仔细分析，还有一些数学的细节可以分析，比如我们为什么不考虑底越界的问题，或者高度不够的问题。可以数学计算出，n 这个界是足够大的。但是这些和算法真的关系不大，不展开了，我也就是大概一想，觉得没问题，没有细究。

继续加油！：）