【每日一题】收集足够苹果的最小花园周长

Tag

【二分枚举答案】【二维网格】【2023-12-24】

题目来源

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

解题思路

方法一：二分枚举答案

思路

通过如下过程，我们可以求出边长为 2n 时，二维网格可以容纳的苹果数量为：

$$2n(n+1)(2n+1)$$

图片来源 【图解】O(1) 做法（Python/Java/C++/Go/JS/Rust）。

随着边长的增大，二维网格可以容纳的苹果数量也在增大。于是我们可以二分枚举二维网格的边长，找出可以容纳 neededApples 个苹果的最小二维网格边长。

二分边界为 [1, 100000]，其中 100000 是根据边长为 2n 的二维网格可以容纳苹果 2n(n+1)(2n+1) 估算得到。

算法

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

复杂度分析

时间复杂度：$O(logm)$，$m=\sqrt[3]{neededApples}$。

空间复杂度：$O(1)$。

写在最后

如果您发现文章有任何错误或者对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度的方法，欢迎评论区交流。

最后，感谢您的阅读，如果有所收获的话可以给我点一个 👍 哦。