2187. 完成旅途的最少時間

思路

1. 接找到最少時間很難。
2. 給定時間限制，判斷公車能否在限制時間內跑到 $\text{totalTrip}$ 很簡單。
3. 時間限制越大，公車就能在這段時間內完成越多旅程。

根據前面這三點，能用二分答案法來做，首先判斷邊界。

• 最好的情況就是每一台公車都跑的快，能瞬間完成旅程，需要花 $\text{totalTrip/n}$ 的時間
• 最壞的情況是把旅途都給一台公車完成，這台公車是速度最快的，需要花 $\text{totalTrip}\times\min\text{(time)}$ 的。

程式碼

二分搜尋

class Solution {
public:
    long long minimumTime(vector<int>& time, int totalTrips) {
        
        auto check = [&](long long limit) {
            // 能否在 limit 的時間限制下，完成 totalTrips 趟旅程;
            int trips = 0;
            for(int t : time) {
                trips += (limit / t);
                if(trips >= totalTrips) return true;
            }
            return false;
        };

        // 最好的情況：公車能瞬間完成運輸，能在一秒就完成一趟旅途
        // 最壞的情況：所有運輸都交給跑的最快的公車，
        // 為什麼不是跑得最慢的？因為一旦公車數量增加，都要比一台的時候好，也一定比單一台最快的公車要完成更多旅途
        long long left = totalTrips / time.size() - 1, right = 1LL * totalTrips * ranges::min(time) + 1; // 開區間
        while(left + 1 < right) {
            long long mid = left + (right - left) / 2;
            (check(mid) ? right : left) = mid;
        }
        return right;
    }
};

複雜度分析

• 時間複雜度：$O(n\log{n})$
• 空間複雜度：$O(1)$