力扣2187.完成旅途的最少时间
朴素做法
- 二分答案
classSolution{longlongcheck(vector<int> time,longlong k){longlong res=0;for(auto t:time) res +=(longlong)k/t;return res;}public:longlongminimumTime(vector<int>& time,int totalTrips){int n = time.size();sort(time.begin(),time.end());longlong l=time[0]-1,r=(longlong)totalTrips*time[0];while(l<r){longlong mid = l + r >>1;if(check(time,mid)<(longlong)totalTrips) l = mid +1;else r = mid;}return l;}};
优化
- 内联函数
- 库函数min
classSolution{public:longlongminimumTime(vector<int>& time,int totalTrips){//内联函数 比外部函数快一倍auto check =[&](longlong x)->bool{longlong res=0;for(int t : time){ res += x/t;if(res >= totalTrips)returntrue;}returnfalse;};//求最小值int min_t = ranges::min(time);longlong l=min_t,r=(longlong)totalTrips*min_t;while(l<r){longlong mid = l + r >>1;//说明当前mid时res >= totalif(check(mid)) r = mid;else l = mid +1;}return r;}};
本文转载自: https://blog.csdn.net/Pisasama/article/details/139627948
版权归原作者 阳光男孩01 所有， 如有侵权，请联系我们删除。
版权归原作者 阳光男孩01 所有， 如有侵权，请联系我们删除。