本文涉及的基础知识点

C++二分查找

LeetCode1870. 准时到达的列车最小时速

给你一个浮点数 hour ，表示你到达办公室可用的总通勤时间。要到达办公室，你必须按给定次序乘坐 n 趟列车。另给你一个长度为 n 的整数数组 dist ，其中 dist[i] 表示第 i 趟列车的行驶距离（单位是千米）。
每趟列车均只能在整点发车，所以你可能需要在两趟列车之间等待一段时间。
例如，第 1 趟列车需要 1.5 小时，那你必须再等待 0.5 小时，搭乘在第 2 小时发车的第 2 趟列车。
返回能满足你准时到达办公室所要求全部列车的 最小正整数 时速（单位：千米每小时），如果无法准时到达，则返回 -1 。
生成的测试用例保证答案不超过 107 ，且 hour 的 小数点后最多存在两位数字 。

示例 1：
输入：dist = [1,3,2], hour = 6
输出：1
解释：速度为 1 时：

• 第 1 趟列车运行需要 1/1 = 1 小时。
• 由于是在整数时间到达，可以立即换乘在第 1 小时发车的列车。第 2 趟列车运行需要 3/1 = 3 小时。
• 由于是在整数时间到达，可以立即换乘在第 4 小时发车的列车。第 3 趟列车运行需要 2/1 = 2 小时。
• 你将会恰好在第 6 小时到达。
  示例 2：
  输入：dist = [1,3,2], hour = 2.7
  输出：3
  解释：速度为 3 时：
• 第 1 趟列车运行需要 1/3 = 0.33333 小时。
• 由于不是在整数时间到达，故需要等待至第 1 小时才能搭乘列车。第 2 趟列车运行需要 3/3 = 1 小时。
• 由于是在整数时间到达，可以立即换乘在第 2 小时发车的列车。第 3 趟列车运行需要 2/3 = 0.66667 小时。
• 你将会在第 2.66667 小时到达。
  示例 3：
  输入：dist = [1,3,2], hour = 1.9
  输出：-1
  解释：不可能准时到达，因为第 3 趟列车最早是在第 2 小时发车。

提示：
n == dist.length
1 <= n <= 10⁵
1 <= dist[i] <= 10⁵
1 <= hour <= 10⁹
hours 中，小数点后最多存在两位数字

二分查找（20241208)

整点发车，意味除最后一辆车外，不足一小时算小时。最后一辆车，可能有小数，需要考虑精度。为了避免处理精度，我们将所有时间乘以speed和100。
极端情况：$\sum$dist 的和是10¹⁰,speed = 10⁷，总用时不超过10¹⁹,可能超过long long范围，不超过unsigned long long。
二分查找类型：寻找首端。
Check函数参数范围：[1,10⁷]
Check函数：总用时小于等于hour。最后一趟车，乘以100;其它车向上取整后，乘以speed*100。hour *100+0.5后取整，再乘以speed。

代码

class Solution {
		public:
			int minSpeedOnTime(vector<int>& dist, double hour) {
				auto Check = [&](int mid) {
					unsigned long long uMax = (unsigned long long)(hour * 100 + 0.5) * mid;
					unsigned long long need = 0;
					for (int i = 0; i + 1 < dist.size(); i++) {
						int cur = dist[i] / mid + (0 != dist[i] % mid);
						need += cur * 100llu * mid;
					}
					need += dist.back() * 100llu;
					return need <= uMax;
				};
				auto res = CBinarySearch<int>(1, 10'000'000).FindFrist(Check);
				if (!Check(res)) { return -1; }
				return res;
			}
		};

二分查找分析精度

double的有效精度是15位有效数字,如果此数大于10⁵，则有10位有效小数。
假定每次相加损失的精度无限接近:10^-10。则累加误差后，有效小数为5位，符合题意。
注意：有的地方用整除，有的地方用除。

代码

class Solution {
		public:
			int minSpeedOnTime(vector<int>& dist, double hour) {
				auto Check = [&](int mid) {
					double need = 0;
					for (int i = 0; i + 1 < dist.size(); i++)
					{
						need += (dist[i] / mid + (0 != dist[i] % mid));
					}
					need += dist.back() / (double)mid;
					return need <= hour;
				};
				auto res = CBinarySearch<int>(1, 1e7).FindFrist(Check);
				if (!Check(res)) { return -1; }
				return res;
			}
		};

二分查找

为了避免处理小数，距离和时间都乘以100。
二分查找类型：寻找首端。
Check函数参数范围：[1,10⁷]，由于向上取整，所以速度大于最大距离和等于最大距离一样。
Check函数：最后一趟车用时，不是整数，向上取整到整数。非最后一趟车不是100的整数倍，向上取整到100的整数倍。返回总用时是否小于等于llHour。
需要判断无解。

注意

一，2.01实际存储的是2.009999。故需要 hour*100+0.5。
二，所有列车运行的时间需要向上取整。
三，发车时间都需要以100为单位，向上取整。
四，最大速度是10⁷，别忘记了乘以100。

向上取整的详细证明

性质一：f可能有小数，其整数部分为n。则
如果小数部分等于0， f <= x，等效与 n<= x，解都是 大于等于n的整数。
否则， f <= x，等效与 n+1<= x，解都是 大于等于n+1的整数。
即等效于 向上取整(f) <=x
一，计算第二辆列车的发车时间，t1是整数，第二辆车的发车时间为100$\times$t1。
need = (float)dis/mid，令need的整数部分除以100为n1，d1=need-100$\times$n1。如果d1为0，则t1=n1,否则t1=n1+1 。
二，其它列车的发车时间类似。
三，计算到达时间。令最后一趟车的发车时间t2，到达时间d2 = t2 + (float)dis/mid 。根据性质一，向上取整后，看是否小于等于llHour。

代码

核心代码

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:
			int minSpeedOnTime(vector<int>& dist, double hour) {
				const long long llHour = hour * 100+0.5; //2.01存储的2.009999
				for (auto& n : dist) {
					n *= 100;
				}
				auto Check = [&](int mid) {
					long long need = 0;
					for (int i = 0; i < dist.size();i++) {
						const int n = dist[i];
						long long cur = n / mid + (0 != n % mid);
						if (i+1 != dist.size()) {
							cur = (n/(100*mid)*100) + 100*( 0 != n%(100*mid));
						}
						need += cur;
					}
					return need <= llHour;
				};
				auto ret = CBinarySearch<int>(1, 10'000'000).FindFrist(Check);
				if (!Check(ret)) return -1;
				return ret;
			}
		};

单元测试

vector<int>dist;
		double hour;
		TEST_METHOD(TestMethod11)
		{
			dist = { 1, 3, 2 }, hour = 6;
			auto res = Solution().minSpeedOnTime(dist, hour);
			AssertEx(1, res);
		}
		TEST_METHOD(TestMethod12)
		{
			dist = { 1, 3, 2 }, hour = 2.7;
			auto res = Solution().minSpeedOnTime(dist, hour);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod13)
		{
			dist = { 1, 3, 2 }, hour = 1.9;
			auto res = Solution().minSpeedOnTime(dist, hour);
			AssertEx(-1, res);
		}
		TEST_METHOD(TestMethod14)
		{
			dist = { 1, 1, 100'000 }, hour =2.01;
			auto res = Solution().minSpeedOnTime(dist, hour);
			AssertEx(10'000'000, res);
		}
		TEST_METHOD(TestMethod15)
		{
			dist = { 5,3,4,6,2,2,7 }, hour = 10.92;
			auto res = Solution().minSpeedOnTime(dist, hour);
			AssertEx(4, res);
		}