锦州市网站建设_网站建设公司_网站备案_seo优化

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

：