力扣2187.完成旅途的最少时间

力扣2187.完成旅途的最少时间

朴素做法

• 二分答案

•   class Solution {
        long long check(vector<int> time,long long k)
        {
            long long res=0;
            for(auto t:time)
                res += (long long)k/t;
            return res;
        }
    public:
        long long minimumTime(vector<int>& time, int totalTrips) {
            int n = time.size();
            sort(time.begin(),time.end());
            long long l=time[0]  - 1,r=(long long)totalTrips*time[0];
            while(l<r)
            {
                long long mid = l + r >> 1;
                if(check(time,mid) < (long long)totalTrips) l = mid + 1;
                else r = mid;
            }
            return l;
        }
    };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22

优化

• 内联函数

• 库函数min

•   class Solution {
    public:
        long long minimumTime(vector<int>& time, int totalTrips) {
            //内联函数 比外部函数快一倍
            auto check = [&](long long x) -> bool
            {
                long long res=0;
                for(int t : time)
                {
                    res += x/t;
                    if(res >= totalTrips) return true;
                }
                return false;
            };
            //求最小值
            int min_t = ranges::min(time);
            long long l=min_t,r=(long long)totalTrips*min_t;
            while(l<r)
            {
                long long mid = l + r >> 1;
                //说明当前mid时res >= total
                if(check(mid)) r = mid;
                else l = mid + 1;
            }
            return r;
        }
    };
  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