2026-05-15：合并有序列表的最小成本。用go语言，给定一个二维整数数组 lists，其中每个 lists[i] 都是非空且按非递减顺序排列的整数序列。

你可以反复进行操作：每次从 lists 里选出两个不同的序列 a = lists[i] 和 b = lists[j]，然后把它们合并成一个新序列。该次合并的费用为：

len(a) + len(b) + abs(median(a) - median(b))

其中：len(x) 表示序列长度；median(x) 表示中位数（先假定序列不变有序，取中间位置；若长度为偶数，则取左侧中间那个元素）。

进行合并后，需要把原来的 a 和 b 从 lists 中移除，并把合并后的有序结果重新插入到 lists 的任意位置。一直重复上述操作，直到 lists 中只剩下一个序列。

任务是：计算把所有子序列最终合并成一个整体有序序列所需的最小总费用，并返回该最小成本。

2 <= lists.length <= 12。

1 <= lists[i].length <= 500。

-1000000000 <= lists[i][j] <= 1000000000。

lists[i] 按照非递减顺序排序。

lists[i].length 的总和不超过 2000。

输入: lists = [[1,3,5],[2,4],[6,7,8]]。

输出: 18。

解释:

合并 a = [1, 3, 5] 和 b = [2, 4]：

len(a) = 3，len(b) = 2

median(a) = 3，median(b) = 2

cost = len(a) + len(b) + abs(median(a) - median(b)) = 3 + 2 + abs(3 - 2) = 6

此时 lists 变为 [[1, 2, 3, 4, 5], [6, 7, 8]]。

合并 a = [1, 2, 3, 4, 5] 和 b = [6, 7, 8]：

len(a) = 5，len(b) = 3

median(a) = 3，median(b) = 7

cost = len(a) + len(b) + abs(median(a) - median(b)) = 5 + 3 + abs(3 - 7) = 12

此时 lists 变为 [[1, 2, 3, 4, 5, 6, 7, 8]]，总成本为 6 + 12 = 18。

题目来自力扣3801。

分步详细过程+复杂度分析

一、基础概念铺垫

1. 合并规则：每次选两个有序列表合并为新有序列表，费用 = 长度和 + 两个列表中位数的绝对差
2. 中位数定义：有序列表，偶数长度取左侧中间元素，奇数长度取正中间元素
3. 二进制掩码：用一个整数表示选中的列表子集（如3个列表，掩码101表示选中第0、2个列表）
4. 总目标：把所有列表合并为1个，求最小总费用

二、算法整体执行步骤（对应你的代码逻辑）

第一步：输入拆分（分治预处理）

因为列表总数n≤12，直接全量计算效率低，代码将所有列表平分为前后两半：

• 示例输入：[[1,3,5],[2,4],[6,7,8]]，n=3
• 前半部分m=1个列表：[[1,3,5]]
• 后半部分n-m=2个列表：[[2,4],[6,7,8]]

第二步：子集合并预处理（calcSorted函数）

对前半部分、后半部分分别计算所有子集的合并结果：

1. 遍历每一个列表，用二进制掩码标记子集
2. 对每一个子集，将其中所有原始列表合并为一个完整的有序数组
3. 存储：每个掩码（子集）对应 → 该子集合并后的完整有序数组

具体效果：

• 前半部分（1个列表）：所有子集（共2¹=2个）都能算出合并后的有序数组
• 后半部分（2个列表）：所有子集（共2²=4个）都能算出合并后的有序数组
• 作用：后续任意组合前后子集，都能直接拿到合并后的数组，不用重复计算

第三步：所有子集的中位数预计算

这是核心优化步骤，提前算出任意子集合并后的中位数，避免DP中重复计算：

1. 遍历所有可能的子集掩码（总共有2ⁿ个，n=3时共8个）
2. 把每个掩码拆分为：前半部分子集 + 后半部分子集
3. 拿到两部分的合并有序数组，调用「寻找两个正序数组中位数」算法
4. 存储：每个子集掩码 → 该子集合并后的中位数

关键意义：

任意两个子集合并时，它们的中位数直接查表获取，极大提升效率。

第四步：状态压缩动态规划（核心求解最小成本）

动态规划定义：

• dp[mask]：将mask代表的所有列表合并为一个数组的最小总费用
• 目标：dp[全1掩码]（所有列表合并完成的最小成本）

DP执行步骤：

1. 初始化

   • 单个列表的掩码（如001/010/100）：无需合并，费用为0
   • 其余掩码初始化为无穷大（表示暂未计算）

2. 遍历所有子集掩码
   从小到大遍历所有掩码，保证计算大子集时，其子集已经算完：

   • 跳过单个列表的掩码
   • 对当前掩码，拆分所有合法的两个不相交子集（j和k，j+k=当前掩码）
   • 计算合并这两个子集的费用：dp[j] + dp[k] + 合并费用
   • 合并费用公式：子集j长度 + 子集k长度 + |j的中位数 - k的中位数|
   • 更新dp[mask]为所有拆分方式中的最小值

3. 最终结果
   全1掩码（所有列表合并）对应的dp值，就是最小总费用。

第五步：示例验证（对应题目输入输出）

输入3个列表：A[1,3,5]、B[2,4]、C[6,7,8]

1. 合并A+B：费用=3+2+|3-2|=6
2. 合并(AB)+C：费用=5+3+|3-7|=12
3. 总费用=6+12=18，与算法计算结果一致。

三、时间复杂度分析

我们基于核心参数计算：

• n：列表总数（≤12）
• L：所有列表总长度（≤2000）

1. 子集合并预处理

• 总子集数：2ⁿ（n≤12 → 4096）
• 每个子集合并：总长度O(L)
• 时间：O(2ⁿ × L)

2. 中位数预计算

• 总子集数：2ⁿ
• 每个中位数计算：O(logL)
• 时间：O(2ⁿ × logL)

3. 动态规划核心

• 总掩码数：2ⁿ
• 每个掩码拆分：O(3ⁿ)（子集拆分的经典复杂度）
• 单次计算：O(1)（查表）
• 时间：O(3ⁿ)

总时间复杂度

O(2ⁿ × L + 3ⁿ)

• n≤12时：3¹²=531441，2¹²×2000=800万，计算量极小，完全满足要求。

四、额外空间复杂度（除输入外的占用空间）

1. 存储子集合并数组

• 总子集数：2ⁿ
• 每个子集存储合并后的数组：总空间O(L)
• 空间：O(2ⁿ + L)

2. 存储中位数、DP数组

• 中位数数组：O(2ⁿ)
• DP数组：O(2ⁿ)

总额外空间复杂度

O(2ⁿ + L)

• 2¹²=4096，L≤2000，空间占用极低。

总结

1. 核心思路：利用状态压缩DP解决小规模（n≤12）的合并最优解问题，通过分治预处理+子集预计算优化效率；
2. 执行流程：拆分列表→预处理所有子集合并结果→预计算所有子集中位数→DP枚举所有合并方式求最小成本；
3. 复杂度：
   • 时间：O(2ⁿ×总长度 + 3ⁿ)，n≤12时效率极高；
   • 额外空间：O(2ⁿ + 总长度)，空间占用极小。

Go完整代码如下：

package main

import (
	"fmt"
	"math"
	"sort"
)

// 88. 合并两个有序数组（创建一个新数组）
func merge(a, b []int) []int {
	i, n := 0, len(a)
	j, m := 0, len(b)
	res := make([]int, 0, n+m)
	for {
		if i == n {
			return append(res, b[j:]...)
		}
		if j == m {
			return append(res, a[i:]...)
		}
		if a[i] < b[j] {
			res = append(res, a[i])
			i++
		} else {
			res = append(res, b[j])
			j++
		}
	}
}

func calcSorted(lists [][]int) [][]int {
	u := 1 << len(lists)
	sorted := make([][]int, u)
	for i, a := range lists {
		highBit := 1 << i
		for s, b := range sorted[:highBit] {
			sorted[highBit|s] = merge(a, b)
		}
	}
	return sorted
}

// 4. 寻找两个正序数组的中位数
func findMedianSortedArrays(a, b []int) int {
	if len(a) > len(b) {
		a, b = b, a
	}

	m, n := len(a), len(b)
	i := sort.Search(m, func(i int) bool {
		j := (m+n+1)/2 - i - 2
		return a[i] > b[j+1]
	}) - 1

	j := (m+n+1)/2 - i - 2
	if i < 0 {
		return b[j]
	}
	if j < 0 {
		return a[i]
	}
	return max(a[i], b[j])
}

func minMergeCost(lists [][]int) int64 {
	n := len(lists)
	m := n / 2
	sorted1 := calcSorted(lists[:m])
	sorted2 := calcSorted(lists[m:])

	u := 1 << n
	half := 1<<m - 1
	median := make([]int, u)
	for i := 1; i < u; i++ {
		// 把 i 分成低 m 位和高 n-m 位
		// 低 half 位去 sorted1 中找合并后的数组
		// 高 n-half 位去 sorted2 中找合并后的数组
		median[i] = findMedianSortedArrays(sorted1[i&half], sorted2[i>>m])
	}

	f := make([]int, u)
	for i := range f {
		if i&(i-1) == 0 {
			continue
		}
		f[i] = math.MaxInt
		for j := i & (i - 1); j > i^j; j = (j - 1) & i {
			k := i ^ j
			f[i] = min(f[i], f[j]+f[k]+abs(median[j]-median[k]))
		}
		f[i] += len(sorted1[i&half]) + len(sorted2[i>>m])
	}
	return int64(f[u-1])
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

func main() {
	lists := [][]int{{1, 3, 5}, {2, 4}, {6, 7, 8}}
	result := minMergeCost(lists)
	fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

from typing import List


def merge(a: List[int], b: List[int]) -> List[int]:
    """88. 合并两个有序数组（创建一个新数组）"""
    i, n = 0, len(a)
    j, m = 0, len(b)
    res = []
    
    while True:
        if i == n:
            res.extend(b[j:])
            return res
        if j == m:
            res.extend(a[i:])
            return res
        if a[i] < b[j]:
            res.append(a[i])
            i += 1
        else:
            res.append(b[j])
            j += 1


def calc_sorted(lists: List[List[int]]) -> List[List[int]]:
    """预计算所有子集合并后的有序数组"""
    u = 1 << len(lists)
    sorted_arr = [[] for _ in range(u)]
    
    for i, a in enumerate(lists):
        high_bit = 1 << i
        for s in range(high_bit):
            sorted_arr[high_bit | s] = merge(a, sorted_arr[s])
    
    return sorted_arr


def find_median_sorted_arrays(a: List[int], b: List[int]) -> int:
    """4. 寻找两个正序数组的中位数（这里返回较大的那半）"""
    if len(a) > len(b):
        a, b = b, a
    
    m, n = len(a), len(b)
    
    # 二分查找 i
    left, right = 0, m
    while left < right:
        mid = (left + right) // 2
        j = (m + n + 1) // 2 - mid - 2
        if j + 1 < n and a[mid] > b[j + 1]:
            right = mid
        else:
            left = mid + 1
    
    i = left - 1
    j = (m + n + 1) // 2 - i - 2
    
    if i < 0:
        return b[j]
    if j < 0:
        return a[i]
    return max(a[i], b[j])


def min_merge_cost(lists: List[List[int]]) -> int:
    """计算最小合并代价"""
    n = len(lists)
    m = n // 2
    
    sorted1 = calc_sorted(lists[:m])
    sorted2 = calc_sorted(lists[m:])
    
    u = 1 << n
    half = (1 << m) - 1
    
    median = [0] * u
    for i in range(1, u):
        median[i] = find_median_sorted_arrays(
            sorted1[i & half],
            sorted2[i >> m]
        )
    
    f = [0] * u
    INF = float('inf')
    
    for i in range(u):
        if i & (i - 1) == 0:
            continue
        f[i] = INF
        j = i & (i - 1)
        while j > (i ^ j):
            k = i ^ j
            f[i] = min(f[i], f[j] + f[k] + abs(median[j] - median[k]))
            j = (j - 1) & i
        
        f[i] += len(sorted1[i & half]) + len(sorted2[i >> m])
    
    return f[u - 1]


def main():
    lists = [[1, 3, 5], [2, 4], [6, 7, 8]]
    result = min_merge_cost(lists)
    print(result)


if __name__ == "__main__":
    main()

C++完整代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <cmath>

using namespace std;

// 88. 合并两个有序数组（创建一个新数组）
vector<int> merge(const vector<int>& a, const vector<int>& b) {
    int i = 0, n = a.size();
    int j = 0, m = b.size();
    vector<int> res;
    res.reserve(n + m);

    while (true) {
        if (i == n) {
            res.insert(res.end(), b.begin() + j, b.end());
            return res;
        }
        if (j == m) {
            res.insert(res.end(), a.begin() + i, a.end());
            return res;
        }
        if (a[i] < b[j]) {
            res.push_back(a[i]);
            i++;
        } else {
            res.push_back(b[j]);
            j++;
        }
    }
}

// 预计算所有子集合并后的有序数组
vector<vector<int>> calcSorted(const vector<vector<int>>& lists) {
    int u = 1 << lists.size();
    vector<vector<int>> sorted(u);

    for (int i = 0; i < lists.size(); i++) {
        int highBit = 1 << i;
        for (int s = 0; s < highBit; s++) {
            sorted[highBit | s] = merge(lists[i], sorted[s]);
        }
    }

    return sorted;
}

// 4. 寻找两个正序数组的中位数（这里返回较大的那半）
int findMedianSortedArrays(vector<int> a, vector<int> b) {
    if (a.size() > b.size()) {
        swap(a, b);
    }

    int m = a.size(), n = b.size();

    // 二分查找 i（等价于 Go 的 sort.Search）
    int left = 0, right = m;
    while (left < right) {
        int mid = (left + right) / 2;
        int j = (m + n + 1) / 2 - mid - 2;
        if (j + 1 < n && a[mid] > b[j + 1]) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }

    int i = left - 1;
    int j = (m + n + 1) / 2 - i - 2;

    if (i < 0) return b[j];
    if (j < 0) return a[i];
    return max(a[i], b[j]);
}

// 计算最小合并代价
long long minMergeCost(const vector<vector<int>>& lists) {
    int n = lists.size();
    int m = n / 2;

    vector<vector<int>> sorted1 = calcSorted(
        vector<vector<int>>(lists.begin(), lists.begin() + m)
        );
    vector<vector<int>> sorted2 = calcSorted(
        vector<vector<int>>(lists.begin() + m, lists.end())
        );

    int u = 1 << n;
    int half = (1 << m) - 1;

    vector<int> median(u);
    for (int i = 1; i < u; i++) {
        median[i] = findMedianSortedArrays(
            sorted1[i & half],
            sorted2[i >> m]
            );
    }

    vector<long long> f(u, 0);
    for (int i = 0; i < u; i++) {
        if ((i & (i - 1)) == 0) {
            continue;
        }
        f[i] = LLONG_MAX;
        for (int j = i & (i - 1); j > (i ^ j); j = (j - 1) & i) {
            int k = i ^ j;
            f[i] = min(f[i], f[j] + f[k] + abs(median[j] - median[k]));
        }
        f[i] += sorted1[i & half].size() + sorted2[i >> m].size();
    }

    return f[u - 1];
}

int main() {
    vector<vector<int>> lists = {{1, 3, 5}, {2, 4}, {6, 7, 8}};
    long long result = minMergeCost(lists);
    cout << result << endl;
    return 0;
}