3801.合并有序列表的最小成本
难度：困难
问题描述：
给你一个二维整数数组lists，其中每个lists[i]是一个按照非递减顺序排序的非空整数数组。
你可以重复选择两个列表a=lists[i]和b=lists[j]（i!=j），并将它们合并。合并a和b的成本为：
len(a)+len(b)+abs(median(a)-median(b))，其中len和median分别表示列表的长度和中位数。
合并a和b后，从lists中移除a和b，并将新的合并后有序列表（元素按从小到大排列）插入到lists中的任意位置。重复此过程直到只剩下一个列表。
返回将所有列表合并为一个有序列表所需的最小总成本。
数组的中位数是指排序后位于中间的元素。如果数组元素数量为偶数，则取左侧中间元素。
示例1：
输入: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。
示例2：
输入:lists=[[1,1,5],[1,4,7,8]]
输出:10
解释:
合并a=[1,1,5]和b=[1,4,7,8]：
len(a)=3，len(b)=4
median(a)=1，median(b)=4
cost=len(a)+len(b)+abs(median(a)-median(b))=3+4+abs(1-4)=10
此时lists变为[[1,1,1,4,5,7,8]]，总成本为10。
示例3：
输入:lists=[[1],[3]]
输出:4
解释:
合并a=[1]和b=[3]：
len(a)=1，len(b)=1
median(a)=1，median(b)=3
cost=len(a)+len(b)+abs(median(a)-median(b))=1+1+abs(1-3)=4
此时lists变为[[1,3]]，总成本为4。
示例4：
输入:lists=[[1],[1]]
输出:2
解释:
总成本为len(a)+len(b)+abs(median(a)-median(b))=1+1+abs(1-1)=2。
提示：
2<=lists.length<=12
1<=lists[i].length<=500
-109<=lists[i][j]<=109
lists[i]按照非递减顺序排序。
lists[i]的元素总和不超过2000。
问题分析：
本问题中cost的计算使用了公式len(a)+len(b)+abs(median(a)-median(b))，公式中的len(a)和len(b)不管怎么合并，都是固定一样的，但abs(median(a)-median(b))对于选择a和b使最后获得最小成本就有讲究了，策略是把数组中中位数最小的两个数组合并，生成新的二维数组之后仍然选中位数最小的两个数组合并，直到只有一个列表为止。特别注意列表作为函数参数传递是传递的引用，函数中对列表参数的改变会带回原列表。
程序如下：
#对选定的两个列表list1和list2进行合并，返回合并生成的列表 def merge_two_lists(list1,list2): a=[] a.extend(list1) a.extend(list2) a.sort() return a #计算一个有序列表的中位数并返回 def get_median(lists): n=len(lists) if n==1: return lists[0] elif n==2: return lists[0] else: if n%2==0: return lists[n//2-1] else: return lists[n//2] #对一个给定的二维数组，返回中位数最小的两个列表的序号 def get_two_min_median(lists): n=len(lists) a=[] for i in lists: a.append(get_median(i)) b=list(enumerate(a)) b.sort(key=lambda x:x[1]) return b[0],b[1] #主程序 lists=eval(input('pls input lists=')) cost=0 while len(lists)>1: a=(m1,n1),(m2,n2) = get_two_min_median(lists) a=list(a) a.sort(key=lambda x:x[0]) index1=a[0][0] median1=a[0][1] index2=a[1][0] median2=a[1][1] m=lists[index1] n=lists[index2] print(f'合并a={m}和b={n}') print(f'len(a)={len(m)}, len(b)={len(n)}, median(a)={median1},median(b)={median2}') cost += len(m) + len(n) + abs(median1 - median2) c=merge_two_lists(m,n) print(f'cost=len(a)+len(b)+abs(median(a)-median(b))={len(m)}+{len(n)}+{abs(median1-median2)}={cost}') lists.remove(m) lists.remove(n) lists.append(c) #print(f'此时lists变为{lists}') print(f'此时lists变为{lists}，总成本为{cost}')运行实例一
pls input lists=[[1,2,3],[4,7,8],[5,9,10,11]]
合并a=[1, 2, 3]和b=[4, 7, 8]
len(a)=3, len(b)=3, median(a)=2,median(b)=7
cost=len(a)+len(b)+abs(median(a)-median(b))=3+3+5=11
此时lists变为[[5, 9, 10, 11], [1, 2, 3, 4, 7, 8]]，总成本为11
合并a=[5, 9, 10, 11]和b=[1, 2, 3, 4, 7, 8]
len(a)=4, len(b)=6, median(a)=9,median(b)=3
cost=len(a)+len(b)+abs(median(a)-median(b))=4+6+6=27
此时lists变为[[1, 2, 3, 4, 5, 7, 8, 9, 10, 11]]，总成本为27
运行实例二
pls input lists=[[2],[5]]
合并a=[2]和b=[5]
len(a)=1, len(b)=1, median(a)=2,median(b)=5
cost=len(a)+len(b)+abs(median(a)-median(b))=1+1+3=5
此时lists变为[[2, 5]]，总成本为5
运行实例三
pls input lists=[[2,4],[7,8,9,10],[3,5]]
合并a=[2, 4]和b=[3, 5]
len(a)=2, len(b)=2, median(a)=2,median(b)=3
cost=len(a)+len(b)+abs(median(a)-median(b))=2+2+1=5
此时lists变为[[7, 8, 9, 10], [2, 3, 4, 5]]，总成本为5
合并a=[7, 8, 9, 10]和b=[2, 3, 4, 5]
len(a)=4, len(b)=4, median(a)=8,median(b)=3
cost=len(a)+len(b)+abs(median(a)-median(b))=4+4+5=18
此时lists变为[[2, 3, 4, 5, 7, 8, 9, 10]]，总成本为18
：
