问题说明为->
我们想用两个扫描仪扫描N个文档。如果S1和S2是扫描仪1和扫描仪2扫描单个文档所花费的时间,请找出扫描所有N个文档所需的最小时间。
: -
S1 = 2, S2 = 4, N = 2
4输出:
解释:这里我们有两种可能。在扫描仪1或在每个扫描仪中扫描一个文档。在这两种情况下所需的时间都是4。
我想出了一个解决方案,我们找到所有的组合并将它们插入集合。最小值将是集合中的第一个元素。
问题是解的时间复杂度为O(n),但可接受的时间复杂度为O(logn)。
我在考虑二进制搜索,但不能想出一个解决方案。
方法应该是什么?
如果可以扫描文档的一小部分,最快的方法是在扫描仪1中扫描N*S2/(S1+S2)
文档,在扫描仪2中扫描N*S1/(S1+S2)
文档。如果这些不是整数,你必须把其中一个四舍五入,另一个四舍五入,这样你就只有两种可能来检查了。这是O(1)而不是O(log n)
我用的是O(log n)的方法。通过对ans/time的二分搜索,我们可以找到最优时间。
对于二分查找,我们需要上界&下界。假设下界为0。现在我们需要找出上界
如果我们用一台扫描仪扫描所有文件,最少需要多少时间?它将是min (S1,S2) * N,对吧?注意:这里我们不使用其他扫描仪,可以扫描文件,而另一个是忙。Somin(S1,S2) * N将是我们的上界。
我们已经有了界限,
下界= 0
上界= min(S1,S2) * N
现在要准时做废话,吃个mid &检查在中间时间内扫描仪1和扫描仪2可以扫描多少文件。当扫描的文档总数达到>= N时,mid可以是ans.
你可以从这里查看BS - https://www.hackerearth.com/practice/algorithms/searching/binary-search/tutorial/