“Offer comes, ask friends to take it! I am participating in the 2022 Spring Recruit Punch card campaign. Click here for more details.”

I. Problem description

You are given an array of time, where time[I] represents how long it takes the ith bus to complete a trip.

Each bus can make multiple trips in a row, which means that a bus can start its next trip as soon as it completes its current trip. Each bus operates independently, which means that multiple buses can operate at the same time without affecting each other.

I’m going to give you an integer totalTrips, which is the total number of trips that all buses have to make. Return the minimum time required to complete at least totalTrips.

Minimum time to complete the journey.

Two, the title requirements

The sample

Input: time = [1,2,3], totalTrips = 5 Output: 3 Explanation: - time t = 1, the number of trips completed by each bus is [1,0,0] respectively. The total number of completed trips is 1 + 0 + 0 = 1. - at time t = 2, the number of journeys completed by each bus is [2,1,0]. The total number of completed trips is 2 + 1 + 0 = 3. - at time t = 3, the number of journeys completed by each bus is [3,1,1]. The total number of completed trips is 3 + 1 + 1 = 5. So the minimum time to complete at least 5 trips is 3.Copy the code

inspection

1. Binary search 2. You are advised to use 20 to 40 minutes for binary searchCopy the code

Third, problem analysis

So the way I thought about it at the beginning is, time t is slowly increasing. The number of trips per bus can be directly used in time/time spent, just return the minimum time. This is also the simplest algorithm, but unfortunately timed out, you can’t optimize it.

Later after the end of the problem to see the big guy’s solution, found that this problem can be solved with dichotomous algorithm, want to break the head did not think:

Here are the steps:

  • The minimum time to complete the journey is 0 (no walking required) and the maximum time is for the fastest bus to complete the journey itself
  • Left = 0, right = time[0]*totalTrips, mid=left+(right-left)/2
  • Mid represents the total amount of time currently spent. We need to calculate the number of completed journeys in mid, sum
  • Sum >=totalTrips, right=mid
  • Sum
  • Exit the loop and return left

Four, coding implementation

class Solution {
public:
    long long minimumTime(vector<int>& time, int totalTrips) {  
        long long int i,sum,n=time.size(),left,right,mid;// Initialize related data
        sort(time.begin(),time.end());// Sort from smallest to largest
        left=0,right=1L* time[0]*totalTrips;// Left edge right edge
        while(left<right)// loop judgment
        {
            mid=left+(right-left)/2;// The median value is mid
            sum=0;// The number of trips is initialized
            for(i=0; i<n; i++)// The cycle of time it takes a bus to complete a journey
            {
                if(time[i]>mid)
                    break;
                sum+=mid/time[i];// Find the number of journeys
            }
            if(sum>=totalTrips)
                right=mid;// Zoom out to the left
            else
                left=mid+1;// Zoom out to the right
        }
        return left;// Output the result}};Copy the code

V. Test results