題目連結:
題目意譯:
你被給定一整數陣列 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 台即可。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。