2023.12.24力扣每日一题——收集足够苹果的最小花园周长

题目来源

力扣每日一题2023.12.24；题序：1954

我的题解

方法一 枚举

假设边长为2n，周长则为8n。
n直接从1开始遍历到$(10^{15}{)}^{\frac{1}{3}}$,为了简化计算，直接将右边界设为100000.
边长为2n的所有苹果之和计算：
对于坐标为(x,y)的树，有|x|+|y|个苹果，所有一块左上角坐标为(n,n)的正方形土地包括的苹果总数为：$S_n={\sum }_{x=?n}^n{\sum }_{y=?n}^n|x|+|y|$。
由于x和y是对称的，所以：
$S_n=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|$
　　$=2(2n+1)(n+1)$

时间复杂度：O(m${}^{\frac{1}{3}}$)
空间复杂度：O(1)

public  long minimumPerimeter(long neededApples) {
        long res=1;
        for(;res<100000;res++){
            if(caulApples(res)<neededApples){
                continue;
            }else{
                break;
            }
        }
        return res*2*4;
    }
    public  long caulApples(long len){
        long res=2*len*(len+1)*(2*len+1);
        return res;
    }

方法二 二分查找

因为Sn是随着n的增大而单调递增的，所以可以使用二分查找找到最小的n，使得Sn>=neededApples

时间复杂度：O(logm)
空间复杂度：O(1)

public  long minimumPerimeter(long neededApples) {
  long left=1,right=100000;  
    long ans=0;  
    while(left<=right){
        long mid=((right-left)>>1)+left;
        long apples=caulApples(mid);
        if(apples>=neededApples){
            ans=mid;
            right=mid-1;
        }else if(apples<neededApples){
            left=mid+1;
        }
    }
    return left*2*4;
}
public  long caulApples(long len){
    long res=2*len*(len+1)*(2*len+1);
    return res;
}

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~