考察： 堆排序+归并排序
错误思路：
枚举每一个可能的序列和,时间复杂度O(n*n^m),铁TLE
参考y总的思路：
参考归并排序的思想,将选出m个元素的最小值之和换成先选出2个、3个、4个元素和的最小值,也就是说我们在M个序列里归并两个序列,选出这两个序列的n个最小和,再依次往下归并.如果暴力的话时间复杂度和上面相同,因此我们可以对a数组先排个序,将b数组与a数组合并,选出其中N个最小值赋值a数组,再合并后面的b数组
时间复杂度(n*(m-1)*logn)
1 #include <iostream> 2 #include <queue> 3 #include <vector> 4 #include <algorithm> 5 using namespace std; 6 typedef pair<int,int> pii; 7 const int N = 2010; 8 int a[N],b[N],c[N],t,m,n; 9 void merge() 10 { 11 priority_queue<pii,vector<pii>,greater<pii> >heap; 12 for(int i=1;i<=n;i++) heap.push({a[1]+b[i],1});//先初始化为a[1]+b[i] 13 int idx = 1; 14 while(idx<=n){ 15 auto it = heap.top(); 16 heap.pop(); 17 int x = it.first; int y = it.second; 18 c[idx++] = x; 19 heap.push({x-a[y]+a[y+1],y+1}); 20 } 21 for(int i=1;i<=n;i++) a[i] = c[i]; 22 } 23 int main() 24 { 25 26 scanf("%d",&t); 27 while(t--) 28 { 29 scanf("%d%d",&m,&n); 30 for(int i=1;i<=n;i++) scanf("%d",&a[i]); 31 sort(a+1,a+n+1); m--; 32 while(m--) 33 { 34 for(int i=1;i<=n;i++) scanf("%d",&b[i]); 35 merge(); 36 } 37 for(int i=1;i<=n;i++) printf("%d ",a[i]); 38 printf("\n"); 39 } 40 return 0; 41 }