如何用二分查找解决双单调递增数组的最小代价求和问题？

首先，我们结合示例明确问题的核心逻辑：
给定两个单调递增数组 x 和 y，我们可以做两种选择：

• 移动 m1 次选取 x 的前 m1 个元素的最后一个（即 x[m1-1]，m1 范围是 0 ≤ m1 ≤ len(x)，m1=0 表示不选 x），每次移动代价1金币，总代价为 m1 * 1；
• 移动 m2 次选取 y 的前 m2 个元素的最后一个（即 y[m2-1]，m2 范围是 0 ≤ m2 ≤ len(y)，m2=0 表示不选 y），每次移动代价2金币，总代价为 m2 * 2；
  我们需要找到满足 (x[m1-1] if m1>0 else 0) + (y[m2-1] if m2>0 else 0) ≥ K 的最小总代价 m1 + 2*m2。（注：如果是前缀和总和≥K的场景，解法逻辑完全一致，只需替换为前缀和数组即可）

二分查找的解法思路 #

因为数组是单调递增的，我们可以通过遍历其中一个数组的所有可能选择，并用二分查找快速定位另一个数组的最小必要选择，从而计算总代价并取全局最小值。

具体步骤如下：

1. 处理边界情况：

   • 只选 x：找到最小的 m1 使得 x[m1-1] ≥ K，代价为 m1。如果 x 的最大值都小于 K，则该情况不可行。
   • 只选 y：找到最小的 m2 使得 y[m2-1] ≥ K，代价为 2*m2。如果 y 的最大值都小于 K，则该情况不可行。

2. 遍历其中一个数组，用二分查找匹配另一个数组：
   我们以遍历 x 的所有可能 m1 为例（遍历 y 的逻辑完全相同）：

   • 对于每个 m1（从1到 len(x)）：
     • 计算 y 需要提供的最小数值：target = K - x[m1-1]。
     • 如果 target ≤ 0：说明仅当前 x 的元素就满足条件，此时 m2=0，总代价为 m1。
     • 如果 target > 0：在 y 中用二分查找找到第一个大于等于 target 的元素，对应的 m2 是该元素的索引+1（因为数组索引从0开始，m2 是移动次数）。
     • 计算当前总代价 m1 + 2*m2，并更新全局最小代价。

3. 可选：遍历 y 的所有可能 m2 再匹配 x：
   这一步是为了确保不遗漏更优解，不过实际遍历其中一个数组已经能覆盖大部分情况，加上会更严谨。

代码示例（Python） #

import bisect

def min_cost(x, y, K):
    min_total = float('inf')
    n, m = len(x), len(y)
    
    # 情况1：只选x
    idx = bisect.bisect_left(x, K)
    if idx < n:
        min_total = min(min_total, idx + 1)
    
    # 情况2：只选y
    idx = bisect.bisect_left(y, K)
    if idx < m:
        min_total = min(min_total, 2*(idx + 1))
    
    # 情况3：选x和y的组合，遍历x的每个m1
    for m1 in range(1, n+1):
        current_x = x[m1-1]
        target = K - current_x
        if target <= 0:
            min_total = min(min_total, m1)
            continue
        # 二分查找y中第一个>=target的元素索引
        idx = bisect.bisect_left(y, target)
        if idx < m:
            m2 = idx + 1
            total = m1 + 2*m2
            min_total = min(min_total, total)
    
    # 情况4：选x和y的组合，遍历y的每个m2（可选，进一步确保最优解）
    for m2 in range(1, m+1):
        current_y = y[m2-1]
        target = K - current_y
        if target <= 0:
            min_total = min(min_total, 2*m2)
            continue
        idx = bisect.bisect_left(x, target)
        if idx < n:
            m1 = idx + 1
            total = m1 + 2*m2
            min_total = min(min_total, total)
    
    return min_total if min_total != float('inf') else -1  # -1表示无法满足条件

# 测试示例
x = [50, 78, 103, 117, 130, 137, 143, 146, 149, 151, 153, 154, 155]
y = [62, 93, 108, 116, 121, 125, 128, 130, 131, 132, 133]
K = 238
print(min_cost(x, y, K))  # 输出11，与示例一致

为什么二分查找适用？ #

因为数组 x 和 y 都是单调递增的，对于任意给定的 target，我们可以用二分查找在 O(log n) 时间内快速定位第一个满足条件的元素。遍历其中一个数组的时间是 O(n)，所以总的时间复杂度是 O(n log m + m log n)，如果优先遍历较短的数组，还能进一步优化运行效率。

内容的提问来源于stack exchange，提问作者var.exe