两台扫描仪扫描N份文档的最小耗时计算及O(logn)解法咨询

核心逻辑 #

我们不需要枚举所有文档分配方案，转而通过二分搜索直接验证「给定时间T是否能完成全部扫描任务」，逐步逼近最小可行时间：

• 如果T时间内可以完成扫描，就尝试寻找更小的可行时间
• 如果T时间内无法完成扫描，就必须增大时间上限

二分边界确定 #

• 左边界left：初始设为0，代表最短可能耗时的下界
• 右边界right：初始设为max(S1, S2) * N，代表最坏情况（所有文档都交给更慢的扫描仪扫描）的耗时

可行性判断逻辑（O(1)复杂度） #

对于任意给定的时间T：

• 扫描仪1最多可扫描 T // S1 份文档
• 扫描仪2最多可扫描 T // S2 份文档
  只要二者之和>= N，说明存在合法分配方案，可以在T时间内完成全部扫描。该判断逻辑的正确性可通过分配区间存在性证明：只要T//S1 + T//S2 >= N，就一定存在分配值x（分给扫描仪1的份数）满足max(x*S1, (N-x)*S2) <= T。

算法复杂度说明 #

二分搜索的总次数为log(max(S1,S2)*N)，每次判断为O(1)，整体时间复杂度为O(logN)，远优于枚举分配方案的O(N)复杂度，可支持N极大的场景。

代码实现示例（Python） #

def min_scan_time(S1: int, S2: int, N: int) -> int:
    left = 0
    right = max(S1, S2) * N
    min_time = right
    while left <= right:
        mid = (left + right) // 2
        total = mid // S1 + mid // S2
        if total >= N:
            min_time = mid
            right = mid - 1
        else:
            left = mid + 1
    return min_time

# 测试示例
print(min_scan_time(2, 4, 2)) # 输出结果为4

内容的提问来源于stack exchange，提问作者Soham Mafidar