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

2023-12-24 14:42:09

Tag

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


题目来源

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


解题思路

方法一:二分枚举答案

思路

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

2 n ( n + 1 ) ( 2 n + 1 ) 2n(n+1)(2n+1) 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 ( l o g m ) O(logm) O(logm) m = n e e d e d A p p l e s 3 m = \sqrt[3]{neededApples} m=3neededApples ?

空间复杂度: O ( 1 ) O(1) O(1)


写在最后

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

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

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

文章来源:https://blog.csdn.net/weixin_54383080/article/details/135180828
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。