本文涉及知识点
贪心 数学
LeetCode1739. 放置盒子
有一个立方体房间，其长度、宽度和高度都等于 n 个单位。请你在房间里放置 n 个盒子，每个盒子都是一个单位边长的立方体。放置规则如下：
你可以把盒子放在地板上的任何地方。
如果盒子 x 需要放置在盒子 y 的顶部，那么盒子 y 竖直的四个侧面都 必须 与另一个盒子或墙相邻。
给你一个整数 n ，返回接触地面的盒子的 最少 可能数量。
示例 1：
输入：n = 3
输出：3
解释：上图是 3 个盒子的摆放位置。
这些盒子放在房间的一角，对应左侧位置。
示例 2：
输入：n = 4
输出：3
解释：上图是 3 个盒子的摆放位置。
这些盒子放在房间的一角，对应左侧位置。
示例 3：
输入：n = 10
输出：6
解释：上图是 10 个盒子的摆放位置。
这些盒子放在房间的一角，对应后方位置。
提示：
1 <= n <= 109
数学
要想第二层有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 等于105，看能否到109。
代码
核心代码
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++**实现。
