题目来源
我的题解
方法一 枚举
假设边长为2n，周长则为8n。
n直接从1开始遍历到 ( 1 0 15 ) 1 3 (10^{15})^\frac{1}{3} (1015)31,为了简化计算，直接将右边界设为100000.
边长为2n的所有苹果之和计算：
对于坐标为(x,y)的树，有|x|+|y|个苹果，所有一块左上角坐标为(n,n)的正方形土地包括的苹果总数为： S n = ∑ x = − n n ∑ y = − n n ∣ x ∣ + ∣ y ∣ S_n=\sum_{x=-n}^{n}\sum_{y=-n}^{n}|x|+|y| Sn=∑x=−nn∑y=−nn∣x∣+∣y∣。
由于x和y是对称的，所以：
S n = 2 ∑ x = − n n ∑ y = − n n ∣ x ∣ S_n=2\sum_{x=-n}^{n}\sum_{y=-n}^{n}|x| Sn=2∑x=−nn∑y=−nn∣x∣
= 2 ∑ x = − n n ( 2 n + 1 ) ∣ x ∣ =2\sum_{x=-n}^{n}(2n+1)|x| =2∑x=−nn(2n+1)∣x∣
= 2 ( 2 n + 1 ) ∑ x = − n n ∣ x ∣ =2(2n+1)\sum_{x=-n}^{n}|x| =2(2n+1)∑x=−nn∣x∣
= 2 ( 2 n + 1 ) ( n + 1 ) =2(2n+1)(n+1) =2(2n+1)(n+1)
时间复杂度：O(m 1 3 ^\frac{1}{3} 31)
空间复杂度：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;
}
有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~
![<span style='color:red;'>力</span><span style='color:red;'>扣</span><span style='color:red;'>每日</span><span style='color:red;'>一</span><span style='color:red;'>题</span>day33[111. 二叉树<span style='color:red;'>的</span><span style='color:red;'>最</span><span style='color:red;'>小</span>深度]](https://img-blog.csdnimg.cn/img_convert/9ef108bb12725c2cf7697039e386c61d.jpeg)
