企业官网建设流程全解析

二级域名怎么做网站备案,南京做网站群的公司,软件开发哪家公司好,企业网站源码cms3801.合并有序列表的最小成本难度#xff1a;困难问题描述#xff1a;给你一个二维整数数组lists#xff0c;其中每个lists[i]是一个按照非递减顺序排序的非空整数数组。你可以重复选择两个列表alists[i]和blists[j]#xff08;i!j#xff09;#xff0c;并将它们合并。合…3801.合并有序列表的最小成本难度困难问题描述给你一个二维整数数组lists其中每个lists[i]是一个按照非递减顺序排序的非空整数数组。你可以重复选择两个列表alists[i]和blists[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)3len(b)2median(a)3median(b)2costlen(a)len(b)abs(median(a)-median(b))32abs(3-2)6此时lists变为[[1,2,3,4,5],[6,7,8]]。合并a[1,2,3,4,5]和b[6,7,8]len(a)5len(b)3median(a)3median(b)7costlen(a)len(b)abs(median(a)-median(b))53abs(3-7)12此时lists变为[[1,2,3,4,5,6,7,8]]总成本为61218。示例2输入:lists[[1,1,5],[1,4,7,8]]输出:10解释:合并a[1,1,5]和b[1,4,7,8]len(a)3len(b)4median(a)1median(b)4costlen(a)len(b)abs(median(a)-median(b))34abs(1-4)10此时lists变为[[1,1,1,4,5,7,8]]总成本为10。示例3输入:lists[[1],[3]]输出:4解释:合并a[1]和b[3]len(a)1len(b)1median(a)1median(b)3costlen(a)len(b)abs(median(a)-median(b))11abs(1-3)4此时lists变为[[1,3]]总成本为4。示例4输入:lists[[1],[1]]输出:2解释:总成本为len(a)len(b)abs(median(a)-median(b))11abs(1-1)2。提示2lists.length121lists[i].length500-109lists[i][j]109lists[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): nlen(lists) if n1: return lists[0] elif n2: return lists[0] else: if n%20: return lists[n//2-1] else: return lists[n//2] #对一个给定的二维数组返回中位数最小的两个列表的序号 def get_two_min_median(lists): nlen(lists) a[] for i in lists: a.append(get_median(i)) blist(enumerate(a)) b.sort(keylambda x:x[1]) return b[0],b[1] #主程序 listseval(input(pls input lists)) cost0 while len(lists)1: a(m1,n1),(m2,n2) get_two_min_median(lists) alist(a) a.sort(keylambda x:x[0]) index1a[0][0] median1a[0][1] index2a[1][0] median2a[1][1] mlists[index1] nlists[index2] print(f合并a{m}和b{n}) print(flen(a){len(m)}, len(b){len(n)}, median(a){median1},median(b){median2}) cost len(m) len(n) abs(median1 - median2) cmerge_two_lists(m,n) print(fcostlen(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)7costlen(a)len(b)abs(median(a)-median(b))33511此时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)3costlen(a)len(b)abs(median(a)-median(b))46627此时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)5costlen(a)len(b)abs(median(a)-median(b))1135此时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)3costlen(a)len(b)abs(median(a)-median(b))2215此时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)3costlen(a)len(b)abs(median(a)-median(b))44518此时lists变为[[2, 3, 4, 5, 7, 8, 9, 10]]总成本为18