本文涉及知识点
贪心 数学
LeetCode1739. 放置盒子
有一个立方体房间，其长度、宽度和高度都等于 n 个单位。请你在房间里放置 n 个盒子，每个盒子都是一个单位边长的立方体。放置规则如下：
你可以把盒子放在地板上的任何地方。
如果盒子 x 需要放置在盒子 y 的顶部，那么盒子 y 竖直的四个侧面都 必须 与另一个盒子或墙相邻。
给你一个整数 n ，返回接触地面的盒子的 最少 可能数量。
示例 1：
输入：n = 3
输出：3
解释：上图是 3 个盒子的摆放位置。
这些盒子放在房间的一角，对应左侧位置。
示例 2：
输入：n = 4
输出：3
解释：上图是 3 个盒子的摆放位置。
这些盒子放在房间的一角，对应左侧位置。
示例 3：
输入：n = 10
输出：6
解释：上图是 10 个盒子的摆放位置。
这些盒子放在房间的一角，对应后方位置。
提示：
1 <= n <= 10
数学
要想第二层有1块，第一层至少3块。
2->5 3->6
4->8 5->9 6->10
7->12…
向量v1的含义是：第一层有v1[i]块，则第二层有i块。
v2[i] 记录 ，第一层有k 块，总共能有多少块。
第一层i块，第二层能有i2块： unpper(v1.begin(),v1,end(),i)-1
v2[i] = v2[i2] +i 。
现在更新到 i 等于10，看能否到10。
代码
核心代码
class Solution {
public:
int minimumBoxes(int n) {
static auto v2 = CreateV2();
return std::lower_bound(v2.begin(), v2.end(), n) - v2.begin();
}
vector<int> CreateV2()
{
vector<int> v1 = { 0,3 };
const int iMax = 1650467;
int x = 3;
for (int j = 2; v1.size() <= iMax; j++)
{
x++;
for (int k = 1; k <= j; k++)
{
v1.emplace_back(++x);
}
}
vector<int> v2 = { 0 };
for (int i = 1; i <= iMax; i++)
{
const int i2 = std::upper_bound(v1.begin(), v1.end(), i) - v1.begin() - 1;
v2.emplace_back(v2[i2] + i);
}
return v2;
}
};
测试用例
template<class T,class T2>
void Assert(const T& t1, const T2& t2)
{
assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
Assert(v1[i], v2[i]);
}
}
int main()
{
{
Solution sln;
;
auto res = sln.minimumBoxes(3);
Assert(3, res);
}
{
Solution sln;
;
auto res = sln.minimumBoxes(4);
Assert(3, res);
}
{
Solution sln;
;
auto res = sln.minimumBoxes(10);
Assert(6, res);
}
}
2023年5月
class Solution {
public:
int minimumBoxes(int n) {
//完整的层次
int leve = 1;
int iCur = 1;
while (n > iCur)
{
n -= iCur;
leve++;
iCur += leve;
}
//挨着边缘放放
int leve2 = 1;
iCur = 1;
while (n >iCur)
{
n -= iCur;
leve2++;
iCur++;
}
return (leve )*(leve - 1) / 2 + leve2;
}
};
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关
下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。