题目描述
You have a cubic storeroom where the width, length, and height of the room are all equal to n
units. You are asked to place n boxes in this room where each box is a cube of unit side length. There are however some rules to placing the boxes:
- You can place the boxes anywhere on the floor.
- If box
x
is placed on top of the boxy
, then each side of the four vertical sides of the boxy
must either be adjacent to another box or to a wall.
Given an integer n
, return the minimum possible number of boxes touching the floor.
样例
Input: n = 3
Output: 3
Explanation: The figure above is for the placement of the three boxes.
These boxes are placed in the corner of the room, where the corner is on the left side.
Input: n = 4
Output: 3
Explanation: The figure above is for the placement of the four boxes.
These boxes are placed in the corner of the room, where the corner is on the left side.
Input: n = 10
Output: 6
Explanation: The figure above is for the placement of the ten boxes.
These boxes are placed in the corner of the room, where the corner is on the back side.
算法
(找规律,贪心) $O(n^{\frac{1}{3}})$
row
: 盒子层数base
: 接触地板的盒子数,next_base = cur_base + (row + 1)
步骤
- 首先在第一个循环中每次循环尝试增加一层盒子 (
sum += base
), 直到盒子总数sum
大于等于n
. (如果等于,直接返回base
就是我们的答案) - 如果不等,可以知道答案就在
(prev_base, base)
这个开区间中,那么尝试看能不能从base
中减少盒子,每减少一个,我们就需要从总数中减少row--
个盒子,看上图中的红线,这是最佳的从base
中减少盒子的方法(贪心),直到我们减少到sum
小于了n
(刚好减过了一个), 那么返回base+1
;或者刚好等于n
那么返回base
时间复杂度
row
的最大值,对应就是第一个循环的循环次数,也就是满足$ x(x+1)(x+2)/6>=n $的x
的最小解,大概是$O(n^{\frac{1}{3}})$。
参考文献
搬运自我的英文题解[C++] my solution w/ some notes, O(n^(1/3))
C++ 代码
class Solution {
public:
int minimumBoxes(int n) {
int sum = 1, base = 1, row = 1;
while (sum < n) {
base += (++row);
sum += base;
}
while (sum > n) {
--base;
sum -= (row--);
}
return base + (sum < n);
}
};