🔗 🟡 2187. Minimum Time to Complete Trips 1641

tags: `Weekly Contest 282` `陣列(Array)` `二分搜尋(Binary Search)`

Now only code is provided, no explanation is given temporarily.

題意

給定一個陣列 $time$ ，其中 $time[i]$ 表示第 $i$ 輛公車完成 一次旅程 所需的時間。

每輛公車可以連續完成多趟旅程，也就是說，一輛公車當前旅程完成後，可以 立即開始 下一趟旅程。每輛公車獨立運行，也就是說可以同時有多輛公車在運行且互不影響。

給定一個整數 $totalTrips$ ，表示所有公車總共應完成的旅程數。返回完成至少 $totalTrips$ 旅程所需的最少時間。

約束條件

$1 \leq \text{time.length} \leq 10^5$
$1 \leq \text{time[i]}, \text{totalTrips} \leq 10^7$

思路：二分搜尋(Binary Search)

<++>

複雜度分析

<++>

class Solution:
    def minimumTime(self, time: List[int], totalTrips: int) -> int:
        def check(t):
            return sum(t//x for x in time) >= totalTrips

        left, right = 1, min(time) * totalTrips
        while left <= right:
            mid = (left + right) // 2
            if check(mid):
                right = mid - 1
            else:
                left = mid + 1
        return left

class Solution {
public:
    long long minimumTime(vector<int>& time, int totalTrips) {
        function<bool(long long)> check = [&](long long t) -> bool {
            long long sum = 0;
            for (int x : time) {
                sum += t / x;
            }
            return sum >= totalTrips;
        };
        long long left = 1;
        long long right = (long long) *min_element(time.begin(), time.end()) * totalTrips;
        while (left <= right) {
            long long mid = (left + right) / 2;
            if (check(mid)) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
};