LeetCode 1739. Building Boxes
LeetCode 1739. Building Boxes
ShenduCC
发布于 2021-03-02 15:24:06
发布于 2021-03-02 15:24:06
https://leetcode.com/problems/building-boxes/ 题意：在一个边长是n的立方体中放n个方块，方块可以叠加，但是被叠加的在下方的方块八面必须挨着墙或者别的方块。 问最底部最少可以放多少个方块。
这是一道找规律的题目，我们可以找出底部方块的个数m和最多可以放n个方块的对应关系。比如 m=1，n=1 m=2，n=2 m=3，n=4 当底部为3块方块的时候，上一层可以再放一块，一共就是4块 m=4，n=5 m=5，n=7 m=6，n=10 m=7，n=11 m=8，n=13
可以从中找出n的通向公式，给出m可以快速算出n。这样对于题目给出的N我就可以做二分，找出最后一个小于等于N的n对应的m就是答案。
那么这个通项公式，怎么算呢，很麻烦。可以找下规律， 1 2 4 5 7 10 11 13 16 20 21 ... 1 2 1 2 3 1 2 3 4 1 ... 找到规律，那就开始写代码把。
class Solution {
public:
long long int a[2005];
long long int b[2005];
void init()
{
for (long long int i = 1; i <= 2000; i++)
{
a[i] = (i * (i + 1)) / 2;
b[i] = (i * (i + 1) * (i + 2)) / 6;
}
}
int fun2(int x)
{
int l = 1;
int r = 2000;
while (l <= r)
{
int mid = (l + r) / 2;
if (x > a[mid])
{
l = mid + 1;
}
else if (x == a[mid])
{
return mid;
}
else
{
r = mid - 1;
}
}
return r;
}
int fun(int n)
{
int l = 1;
int r = a[2000];
while (l <= r)
{
long long int mid = (l + r) / 2;
int index = fun2(mid);
int m = mid - a[index];
long long int y = b[index] + (m * (m + 1 )) / 2;
if (n > y)
{
l = mid + 1;
}
else if (n == y)
{
return mid;
}
else
{
r = mid - 1;
}
}
return l;
}
int minimumBoxes(int n) {
init();
return fun(n);
}
};本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2021-02-20 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读