文章目录
1. 题目
2. 解题
1. 题目
有一个立方体房间,其长度、宽度和高度都等于 n 个单位。
请你在房间里放置 n 个盒子,每个盒子都是一个单位边长的立方体。放置规则如下:
你可以把盒子放在地板上的任何地方。
如果盒子 x 需要放置在盒子 y 的顶部,那么盒子 y 竖直的四个侧面都 必须 与另一个盒子或墙相邻。
给你一个整数 n ,返回接触地面的盒子的 最少 可能数量。
示例 1:
输入:n = 3 输出:3 解释:上图是 3 个盒子的摆放位置。 这些盒子放在房间的一角,对应左侧位置。
2. 解题
- 根据题意,靠着墙角是最好的方法
- 先假设这个完整的斜坡能摆满,多少层能超过 n
- 然后多余出来的,第一次增加一个底部的可以摆 1 个,第二次增加一个底部的可以增加 2 个积木,依次类推
class Solution { public: int minimumBoxes(int n) { int ct = 1, layer = 1; while(ct < n) { layer++; ct += layer*(layer+1)/2;//每一层的个数 } if(ct == n) return layer*(layer+1)/2; ct -= layer*(layer+1)/2; int left = n-ct;//多出来的 layer--; int bottom = layer*(layer+1)/2, delta = 1; while(left>0) { bottom++;//每放下一个底部积木 left -= delta++;//可以依次增加放置积木1,2,3,4。。。个 } return bottom; } };
0 ms 5.9 MB C++