力扣1870.准时到达的列车最小世俗
-
二分答案
- 上界为什么取max_v * 100?
- 注意到数据范围有一句话 ”
hours中，小数点后最多存在两位数字” - 因此再额外扩两位即可
- 注意到数据范围有一句话 ”
- r = max_v * 100
- 上界为什么取max_v * 100?
-
class Solution {public:int minSpeedOnTime(vector<int>& dist, double hour) {auto check = [&](int x) -> bool{double t=0;int n = dist.size();for(int i=0;i<n;i++){if(i != n-1) t += (dist[i]-1)/x + 1;else t += (double)dist[i]/x;if(t > hour) return false;}return true;};int max_v = ranges::max(dist);int l = 1,r = max_v*100;while(l<r){int mid = l + r >> 1;if(check(mid)) r = mid;else l = mid + 1;}cout<<l<<endl;if(check(l)) return l;else return -1;}};
