問題宣告是->
我們想用兩臺掃描儀來掃描N份檔案。如果S1和S2是掃描儀1和掃描儀2掃描一份檔案所需的時間，請找出掃描所有N份檔案所需的最少時間。
例子：-
S1 = 2, S2 = 4, N = 2
輸出。4
解釋。這里我們有兩種可能性。 要么在掃描儀1中掃描兩個檔案，要么 在每個掃描儀中掃描一份檔案。 在這兩種情況下，所需的時間都是4。
我想出了一個解決方案，我們找到所有的組合并將它們插入到集合中。最小值將是這個集合中的第一個元素。
問題是該解決方案的時間復雜度為 O(n)，但公認的時間復雜度為 O(logn)。
我正在考慮二進制搜索的思路，但無法想出一個解決方案。
應該采用什么方法呢？
uj5u.com熱心網友回復：
如果你能掃描一個檔案的一部分，最快的方法是在掃描儀1中掃描N*S2/(S1 S2)檔案，而在掃描儀2中掃描N*S1/(S1 S2)檔案。而如果這些不是整數，你必須將其中一個四舍五入，一個四舍五入，這樣你就只有兩種可能性可以檢查。這就是O(1)，而不是O(log n)。
uj5u.com熱心網友回復：
好吧，我分享的是O(log n)的方法。通過對ans/time的二進制搜索，我們可以找到最佳時間。
對于二進制搜索，我們需要上界& 下界。讓我們假設下限為0，現在我們需要找出上限。
如果我們用一臺掃描儀掃描所有的檔案，所需的最小時間將是多少。它將是min (S1,S2) * N，對嗎？注意：在這里，我們沒有使用其他的掃描儀，因為它可能在另一臺掃描儀忙碌時掃描檔案。所以min(S1,S2) * N將是我們的上界。
我們已經得到了我們的界限，
下限是什么？
下界=0 上界=min(S1,S2) * N 現在在時間上做BS，取一個中間的&；檢查在中間時間內用掃描儀1掃描儀2能掃描多少檔案。 只要掃描的檔案總數達到>=N，那么中間值就可能是答案。
. 你可以從這里檢查BS - https://www.hackerearth.com/practice/algorithms/searching/binary-search/tutorial/
標籤：