【C++二分查找】1954. 收集足够苹果的最小花园周长

本文涉及的基础知识点

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

代码

核心代码

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++**实现。