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

朴素做法

• 二分答案

•   class Solution {
        long long check(vector time,long long k)
        {
            long long res=0;
            for(auto t:time)
                res += (long long)k/t;
            return res;
        }
    public:
        long long minimumTime(vector& 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
                long long mid = l + r >> 1;
                if(check(time,mid) < (long long)totalTrips) l = mid + 1;
                else r = mid;
            }
            return l;
        }
    };
  

  优化

  • 内联函数

  • 库函数min

  •   class Solution {
      public:
          long long minimumTime(vector& 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
                  long long mid = l + r >> 1;
                  //说明当前mid时res >= total
                  if(check(mid)) r = mid;
                  else l = mid + 1;
              }
              return r;
          }
      };