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

English Version

题目描述

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

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

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

|x| 的值定义为：

如果 x >= 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¹⁵

解法

方法一：数学 + 枚举

假设正方形右上角坐标为 $(n, n)$，那么它的边长为 $2n$，周长为 $8n$，里面的苹果总数为：

$$ \begin{aligned} &\sum_{x=-n}^{n} \sum_{y=-n}^{n} |x| + |y| \ \end{aligned} $$

由于 $x$ 和 $y$ 是对称的，所以可以化简为：

$$ \begin{aligned} &\sum_{x=-n}^{n} \sum_{y=-n}^{n} |x| + |y| \ &= 2 \sum_{x=-n}^{n} \sum_{y=-n}^{n} |x| \ &= 2 \sum_{x=-n}^{n} (2n + 1) |x| \ &= 2 (2n + 1) \sum_{x=-n}^{n} |x| \ &= 2n(n+1)(2n+1) \end{aligned} $$

所以，我们只需要枚举 $n$，直到找到第一个满足 $2n(n+1)(2n+1) \geq neededApples$ 的 $n$ 即可。

时间复杂度 $O(m^{\frac{1}{3}})$，其中 $m$ 为 $neededApples$ 的值。空间复杂度 $O(1)$。

Python3

class Solution:
    def minimumPerimeter(self, neededApples: int) -> int:
        x = 1
        while 2 * x * (x + 1) * (2 * x + 1) < neededApples:
            x += 1
        return x * 8

Java

class Solution {
    public long minimumPerimeter(long neededApples) {
        long x = 1;
        while (2 * x * (x + 1) * (2 * x + 1) < neededApples) {
            ++x;
        }
        return 8 * x;
    }
}

C++

class Solution {
public:
    long long minimumPerimeter(long long neededApples) {
        long long x = 1;
        while (2 * x * (x + 1) * (2 * x + 1) < neededApples) {
            ++x;
        }
        return 8 * x;
    }
};

Go

func minimumPerimeter(neededApples int64) int64 {
	var x int64 = 1
	for 2*x*(x+1)*(2*x+1) < neededApples {
		x++
	}
	return 8 * x
}

TypeScript

function minimumPerimeter(neededApples: number): number {
    let x = 1;
    while (2 * x * (x + 1) * (2 * x + 1) < neededApples) {
        ++x;
    }
    return 8 * x;
}

方法二：二分查找

我们也可以二分枚举 $n$，时间复杂度 $O(\log m)$。

Python3

class Solution:
    def minimumPerimeter(self, neededApples: int) -> int:
        l, r = 1, 100000
        while l < r:
            mid = (l + r) >> 1
            if 2 * mid * (mid + 1) * (2 * mid + 1) >= neededApples:
                r = mid
            else:
                l = mid + 1
        return l * 8

Java

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

C++

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

Go

func minimumPerimeter(neededApples int64) int64 {
	var l, r int64 = 1, 100000
	for l < r {
		mid := (l + r) >> 1
		if 2*mid*(mid+1)*(2*mid+1) >= neededApples {
			r = mid
		} else {
			l = mid + 1
		}
	}
	return l * 8
}

TypeScript

function minimumPerimeter(neededApples: number): number {
    let l = 1;
    let r = 100000;
    while (l < r) {
        const mid = (l + r) >> 1;
        if (2 * mid * (mid + 1) * (2 * mid + 1) >= neededApples) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return 8 * l;
}