Leetcode.1954 收集足够苹果的最小花园周长

题目链接

Leetcode.1954 收集足够苹果的最小花园周长 Rating ： 1759

题目描述

给你一个用无限二维网格表示的花园，每一个 整数坐标处都有一棵苹果树。整数坐标 (i, j)处的苹果树有 $|i|+|j|$ 个苹果。

你将会买下正中心坐标是 (0, 0)的一块 正方形土地 ，且每条边都与两条坐标轴之一平行。

给你一个整数 neededApples，请你返回土地的 最小周长 ，使得 至少 有 neededApples个苹果在土地 里面或者边缘上。

$|x|$ 的值定义为：

• 如果 $x\ge 0$ ，那么值为 $x$
• 如果 $x<0$ ，那么值为 $-x$

示例 1：

输入：neededApples = 1
输出：8
解释：边长长度为 1 的正方形不包含任何苹果。
但是边长为 2 的正方形包含 12 个苹果（如上图所示）。
周长为 2 * 4 = 8 。

示例 2：

输入：neededApples = 13
输出：16

示例 3：

输入：neededApples = 1000000000
输出：5040

提示：

• $1<=neededApples<=10^{15}$

解法：推公式 + 二分查找

我们可以发现规律：每一层的苹果个数都等于 红色的部分 * 4

• 第 0 层，苹果个数为 $4\ast 0$
• 第 1 层，苹果个数为 $4\ast (2+1)$
• 第 2 层，苹果个数为 $4\ast (4+3+2+3)$
• 第 3 层，苹果个数为 $4\ast (6+5+4+3+4+5)$
• …
• 第 n 层，苹果的个数为 $4\ast ((2n+(2n-1)+...+(n+1))+(n+(n+1)+...+(2n-1)))$，即 $4\ast (((3n+1)\ast n/2)+((3n-1)\ast n/2))$，最终化简为 $12n^2$。

一个 n 层正方形所包含的苹果数量为：$12\ast 0^2+12\ast 1^2+12\ast 2^2+...+12\ast n^2=12\ast (0^2+1^2+2^2+...+n^2)=12\ast (n\ast (n+1)\ast (2n+1))/6$，最终化简为 $2n\ast (n+1)\ast (2n+1)$。

所以我们只需要通过 二分 的方式，查找第一个大于等于 $neededApples$ 的 n 层正方形即可。

这里的 n 其实是 $\frac{1}{8}$的周长，所以最后返回 $8\ast n$即可。

时间复杂度：$O(logn)$

C++代码：

using LL = long long;

class Solution {
public:    
    long long minimumPerimeter(long long neededApples) {
        LL l = 0 , r = 1e5;
        while(l < r){
            LL mid = (l + r) >> 1;
            if((2 * mid) * (mid + 1) * (2*mid + 1) >= neededApples) r = mid;
            else l = mid + 1;
        }
        return l * 8;
    }
};