1739 - 放置盒子 - 模拟 - 贪心 - 数学

欢迎关注更多精彩
关注我,学习常用算法与数据结构,一题多解,降维打击。

题目描述

[1739] 放置盒子

题目描述

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

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

示例 1:
在这里插入图片描述

输入:n = 3
输出:3
解释:上图是 3 个盒子的摆放位置。
这些盒子放在房间的一角,对应左侧位置。
示例 2:
在这里插入图片描述

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

在这里插入图片描述

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

提示:

1 <= n <= 10^9

Related Topics
  • 模拟
  • 贪心
  • 数学
  • 题目剖析&信息挖掘

    此题模板比较大,一般需要找到某种数学上的规律,然后通过模拟或动态规划解决。

    解题思路

    方法一 模拟+贪心+数学

    分析

    根据题意,先举几个特殊例子看看。

    可以发现我们在放置盒子时,应该尽量与多的盒子贴近,以求上层可以放置更多的盒子。

    从上面几个例子中可看出,在数量正好是1,4,10… 1+3+6+10+…+(1+n)*n/2时形状是完美的。

    我们称像上面这样正好呈阶梯的形状为完美形状。

    如果不是这些数量的话,可以从某一个特殊例子开始往上构造。

    比如在这4个基础上再放置物体。

    到这里我们可以发现一些规律。

    在已经放置了2层(完美形状)情况下,每次都是从最底下开始,先往上放一个,再放2个,再3个。

    推广到一般情况,如果当前已经放置了一个x-1层的完美形状。

    那么接下来要放的就是斜向上放1个, 2个 ,3个 。。。x个。

    下面我们看一下最底下个数与总数的关系。

    底下个数 n集合 n的个数
    1 1 1
    2 2 1
    3 3,4 2
    4 5 1
    5 6,7 2
    6 8,9,10 3
    7 11 1
    8 12,13 2
    9 14,15,16 3
    10 17,18,19,20 4
    11 21 1
    12 22,23 2
    13 24,25,26 3
    14 27,28,29,30 4
    15 31,32,33,34,35 5
    .。。 。。。 。。。

    可看出规律,对于每一个底部数量,n的个数是呈等差数列变化的,从1到x1, 再从 从1到x2, 再从1到x3, 再从1到x4 … x = [1,2,3,4,…n]

    总结一下就是每次往底部放一个,接下还可以放置y个(包括放在底部那个)使得底部数量不变化。这个y是遵从上述的多个等差数列分布的。

    思路

    func minimumBoxes(n int) int {
    	ans := 0
    	for step:=1;n>0;step++ { // 枚举当前层数,直到放到N个。
    		for i:=1;i<=step&&n>0;i++ { // 每次底部放置一个,接下来放置i个。直到放置n个。
    			n-=i // 接下来放置i个
    			ans++ // 底部旋转一个。
    		}
    	}
    
    	return ans;
    }
    

    注意

    • n比较大,用减法不会溢出。

    知识点

    • 模拟
    • 贪心
    • 数学

    复杂度

    • 时间复杂度:O(sqrt(n))
    • 空间复杂度:O(1)

    代码实现

    func minimumBoxes(n int) int {
    	ans := 0
    	for step:=1;n>0;step++ { // 枚举当前层数,直到放到N个。
    		for i:=1;i<=step&&n>0;i++ { // 每次底部放置一个,接下来放置i个。直到放置n个。
    			n-=i // 接下来放置i个
    			ans++ // 底部旋转一个。
    		}
    	}
    
    	return ans;
    }
    

    本人码农,希望通过自己的分享,让大家更容易学懂计算机知识。
    在这里插入图片描述

    1赞