保持数组A相对顺序插入B元素以最小化逆序数的问题求助

你的问题出在局部贪心选择当前最小元素，没有考虑全局逆序对的累积影响。归并排序式的合并策略是为了得到整体有序数组，但在这个问题中，我们需要在保持A相对顺序的前提下最小化逆序数，两者目标并不一致。

核心分析 #

逆序数由三部分组成：

1. A内部的逆序数：固定不变，因为A的相对顺序必须保留。
2. B内部的逆序数：最小为0，只需将B升序排序即可消除内部逆序。
3. A与B之间的逆序数：这是优化的核心，需要通过合理的合并策略最小化。

对于A中元素x和B中元素y：

• 若x < y：x在y前时无逆序，y在x前时产生1个逆序。
• 若x > y：y在x前时无逆序，x在y前时产生1个逆序。

我们的目标是在保持A、B各自顺序的前提下，最大化满足上述无逆序的情况。

正确方法：动态规划+贪心回溯 #

步骤：

1. 计算A内部逆序数：这部分是固定成本，后续无需考虑。
2. 升序排序B：消除B内部逆序，为后续合并做准备。
3. 动态规划计算最小A-B逆序数：
   • 定义dp[i][j]为合并A的前i个元素和B的前j个元素的最小A-B逆序数。
   • 状态转移：
     • 选择放入A的第i个元素：新增逆序对为B前j个元素中大于A[i-1]的数量，即dp[i][j] = dp[i-1][j] + cnt_b_greater。
     • 选择放入B的第j个元素：新增逆序对为A前i个元素中大于B[j-1]的数量，即dp[i][j] = dp[i][j-1] + cnt_a_greater。
     • 取两者最小值作为dp[i][j]的结果。
4. 回溯得到合并序列：从dp[n][n]倒推，判断每一步是选择放入A还是B的元素，最终反转得到正确顺序。

代码实现（Python） #

def count_internal_inversions(arr):
    # 计算数组内部逆序数（暴力法，适合小规模数组）
    n = len(arr)
    count = 0
    for i in range(n):
        for j in range(i + 1, n):
            if arr[i] > arr[j]:
                count += 1
    return count

def merge_min_inversions(A, B):
    n = len(A)
    inv_A = count_internal_inversions(A)
    B_sorted = sorted(B)
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    A_sorted_prefix = []
    import bisect

    # 填充dp表
    for i in range(1, n + 1):
        bisect.insort(A_sorted_prefix, A[i-1])
        for j in range(1, n + 1):
            # 计算放入A[i-1]的新增逆序对
            cnt_b_greater = j - bisect.bisect_right(B_sorted, A[i-1], 0, j)
            option1 = dp[i-1][j] + cnt_b_greater
            # 计算放入B_sorted[j-1]的新增逆序对
            cnt_a_greater = i - bisect.bisect_right(A_sorted_prefix, B_sorted[j-1])
            option2 = dp[i][j-1] + cnt_a_greater
            dp[i][j] = min(option1, option2)
    
    # 回溯生成合并序列
    res = []
    i, j = n, n
    while i > 0 or j > 0:
        if i == 0:
            res.append(B_sorted[j-1])
            j -= 1
        elif j == 0:
            res.append(A[i-1])
            i -= 1
        else:
            cnt_b_greater = j - bisect.bisect_right(B_sorted, A[i-1], 0, j)
            if dp[i][j] == dp[i-1][j] + cnt_b_greater:
                res.append(A[i-1])
                i -= 1
                idx = bisect.bisect_left(A_sorted_prefix, A[i])
                del A_sorted_prefix[idx]
            else:
                res.append(B_sorted[j-1])
                j -= 1
    res.reverse()
    total_inv = inv_A + dp[n][n]
    return res, total_inv

# 测试反例
A = [99999, 1, 2, 3]
B = [5, 6, 7, 8]
merged, total_inv = merge_min_inversions(A, B)
print("合并序列:", merged)
print("总逆序数:", total_inv)

# 测试第一个示例
A2 = [5, 4, 2, 1]
B2 = [8, 3, 6, 7]
merged2, total_inv2 = merge_min_inversions(A2, B2)
print("合并序列:", merged2)
print("总逆序数:", total_inv2)

结果验证 #

• 反例中得到合并序列[99999, 1, 2, 3, 5, 6, 7, 8]，总逆序数7，与预期一致。
• 第一个示例中，代码会生成逆序数最小的合并序列（可能与你给出的示例序列不同，但逆序数相同）。

内容的提问来源于stack exchange，提问作者Jeremy Khoo