前往
大廳
主題

LeetCode - 2594. Minimum Time to Repair Cars 解題心得

Not In My Back Yard | 2024-02-20 12:00:01 | 巴幣 0 | 人氣 58

題目連結:


題目意譯:
你被給定一整數陣列 ranks,其代表著一些技師的階級。ranksi 為第 i 位技師的階級。一個有著階級 r 的技師可以在 r × n ^ 2 分鐘內修理 n 輛車。

你也同時被給定另一個整數 cars,其代表車庫裡等待修理的車子總數。

回傳修理所有車子最少所需的時間。

注:所有技師可以同時修理車子。

限制:
1 ≦ ranks.length ≦ 10 ^ 5
1 ≦ ranks[i] ≦ 100
1 ≦ cars ≦ 10 ^ 6



範例測資:
範例 1:
輸入: ranks = [4,2,3,1], cars = 10
輸出: 16
解釋:
- 第一個技師將修理兩輛車子。所需時間為 4 × 2 × 2 = 16 分鐘。
- 第二個技師將修理兩輛車子。所需時間為 2 × 2 × 2 = 8 分鐘。
- 第三個技師將修理兩輛車子。所需時間為 3 × 2 × 2 = 12 分鐘。
- 第四個技師將修理四輛車子。所需時間為 1 × 4 × 4 = 16 分鐘。
可以證明所有車子無法在少於 16 分鐘內修理完。

範例 2:
輸入: ranks = [5,1,8], cars = 6
輸出: 16
解釋:
- 第一個技師將修理一輛車子。所需時間為 5 × 1 × 1 = 5 分鐘。
- 第二個技師將修理四輛車子。所需時間為 1 × 4 × 4 = 16 分鐘。
- 第三個技師將修理一輛車子。所需時間為 8 × 1 × 1 = 8 分鐘。
可以證明所有車子無法在少於 16 分鐘內修理完。


解題思維:
對「答案」進行二分搜即可,如這題。要檢查現在猜的答案「對不對」很單純,掃過所有技師來算出他們各自可以在允許時間(即你現在猜的答案)可以修多少車子,然後把這些數字加總並判斷有沒有至少 cars 台即可。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作