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

题目

image-20241002162306525

思路

思路来自leetcode的题解

1870. 准时到达的列车最小时速 - 力扣（LeetCode）

最直接的收获是浮点数运算的时候会出现误差，下面同样是摘自题解中的解释，

由于双精度浮点数无法准确表示诸如 2.01 这样的小数，我们在计算 2.01×100 时，算出的结果不是 201，而是 200.99999999999997 这样的数。

所以代码不能直接转成整数，而是要 round 一下。

round（）的作用简单来讲就是四舍五入

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    int minSpeedOnTime(vector<int>& dist, double hour) {
	//准时到达的列车时速
	int n = dist.size();
	long long h100 = round(hour * 100);
	long long delta = h100 - (n - 1) * 100;
	if (delta <= 0) return -1; //无法到达终点

	int max_dist = ranges::max(dist);
	if (h100 <= n * 100) //特别判断
	{
		return max(max_dist, (int)((dist.back() * 100 - 1) / delta + 1));
	}   

	auto check = [&](int v) -> bool {
		long long t = 0;
		for (int i = 0; i < n - 1; i++) {
			t += (dist[i] - 1) / v + 1;
		}
		return (t * v + dist.back()) * 100 <= h100 * v;
		};

	int h = h100 / (n * 100);
	int left = 0, right = (max_dist - 1) / h + 1;
	while (left + 1 < right) {
		int mid = (left + right) / 2;
		(check(mid) ? right : left) = mid;
	}
	return right;
    }
};