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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

#include <iostream>
#include <vector>

class Solution {
public:
    long long minimumTime(std::vector<int>& time, int totalTrips) {
        int n = time.size();
        if (n == 1) {
            return (long long)time[0] * totalTrips;
        }
        
        long long left, right, mid, sum = 0;
        int min_time = 0x3fff'ffff;
        for (int i : time) {
            min_time = std::min(i, min_time);
        }
        right = (long long)totalTrips * min_time + 1;
        left = (right - 1) / n;
        
        for (long long mid = (left + right) / 2; right > left; mid = (left + right) / 2) {
            if (maxTrips(time, mid, totalTrips)) {
                right = mid;
            }
            else {
                left = mid + 1;
            }
        }
        
        return left;
    }
    
private:
    bool maxTrips(std::vector<int>& time, long long t, int totalTrips) {
        int trips = 0;
        for (int i : time) {
            trips += t / i;
            if (trips >= totalTrips) {
                return true;
            }
        }
        return false;
    }
};