本文涉及的基础知识点

C++二分查找

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

给你一个用无限二维网格表示的花园，每一个 整数坐标处都有一棵苹果树。整数坐标 (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¹⁵

二分查找

边长的一半为s的花园的苹果数Cnt：

所有坐标(x,y)的|x|+|y|之和。即所有|x|之和 +所有|y|之和。由于是以(0,0)为中心的正方形，故两者相等。

令t = (2

×

\times

×s+1)

×

\times

× 2

x为1或-1坐标数为：t,和为 1

×

\times

× t,

x为2或-2的坐标数为：t,和为 2

×

\times

×t,

⋮

\vdots

⋮

故|x|的和为：(1+s )/2

×

s

×

t

\times s \times t

×s×t

故Cnt(s)的返回值为：(s+1)

×

s

×

t

\times s \times t

×s×t

显然Cnt(s) > s³ 故边长10⁵的果园苹果数大于10⁵

二分查找类型：寻找首端

Check函数的参数范围：[1,10⁵]

Check函数：Cnt(mid) >= neededApples

返回值：二分的返回值

×

\times

× 8

代码

核心代码

<code>template<class INDEX_TYPE>

class CBinarySearch

{ -- -->

public:

CBinarySearch(INDEX_TYPE iMinIndex, INDEX_TYPE iMaxIndex):m_iMin(iMinIndex),m_iMax(iMaxIndex) { }

template<class _Pr>

INDEX_TYPE FindFrist( _Pr pr)

{

auto left = m_iMin - 1;

auto rightInclue = m_iMax;

while (rightInclue - left > 1)

{

const auto mid = left + (rightInclue - left) / 2;

if (pr(mid))

{

rightInclue = mid;

}

else

{

left = mid;

}

}

return rightInclue;

}

template<class _Pr>

INDEX_TYPE FindEnd( _Pr pr)

{

int leftInclude = m_iMin;

int right = m_iMax + 1;

while (right - leftInclude > 1)

{

const auto mid = leftInclude + (right - leftInclude) / 2;

if (pr(mid))

{

leftInclude = mid;

}

else

{

right = mid;

}

}

return leftInclude;

}

protected:

const INDEX_TYPE m_iMin, m_iMax;

};

class Solution {

public:

long long minimumPerimeter(long long neededApples) {

auto Check = [&](long long mid) {

return Cnt(mid) >= neededApples;

};

return CBinarySearch<long long>(1, 100'000).FindFrist(Check)*8;

}

inline long long Cnt(long long s) {

auto t = (2 * s + 1) * 2;

return (s + 1) * s * t; };

};

单元测试

long long neededApples;

TEST_METHOD(TestMethod13)

{

neededApples = 1;

auto res = Solution().minimumPerimeter(neededApples);

AssertEx(8LL, res);

}

TEST_METHOD(TestMethod14)

{

neededApples = 13;

auto res = Solution().minimumPerimeter(neededApples);

AssertEx(16LL, res);

}

TEST_METHOD(TestMethod15)

{

neededApples = 1000000000;

auto res = Solution().minimumPerimeter(neededApples);

AssertEx(5040LL, res);

}

TEST_METHOD(TestMethod16)

{

neededApples = 1e15+0.5;

auto res = Solution().minimumPerimeter(neededApples);

AssertEx(503968LL, res);

}

扩展阅读

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。

https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程

https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者 操作系统：win10 开发环境： VS2022 C++17

如无特殊说明，本算法用**C++**实现。