1 3 4 5 1 2 3 4 5 6 7 8 1 2 3 4
75
题解
假设任意两层为集合A B(从大到小排序）对于B集合的元素B[i]，显然它和A[1]组合值最大，
如果B[i]+A[j]是前K大值中的一个，那么B[i]+A[k](1<=k < j)必然也是前K大的，
所以B[i]+A[j]被选则B[i]+A[j-1]之前就被选了，
所以优先队列中只需维护Size(B)个元素，首先把A[1]+B[i]全部进队，
每次从队首拿出一个组合(i,j)(表示A[i]+B[j])，把A[i+1]+B[j]进队，
直到拿出K个元素为止，即为这两个集合合并的前K大
n层的话只要把每次得到的结果和其他层按照这样处理就可以了
AC代码
1 #include <cstdio> 2 #include <cmath> 3 #include <cstring> 4 #include <cstdlib> 5 #include <iostream> 6 #include <sstream> 7 #include <algorithm> 8 #include <string> 9 #include <queue> 10 #include <vector> 11 using namespace std; 12 const int maxn= 1005; 13 const double eps= 1e-6; 14 const int inf = 0x3f3f3f3f; 15 typedef long long ll; 16 int k,n,m; 17 vector<int> a[maxn]; 18 vector<int> ans,d; 19 int cmp(int a,int b) 20 { 21 return a>b; 22 } 23 struct node 24 { 25 int i,j,val; 26 node(){} 27 node(int i,int j,int val):i(i),j(j),val(val){} 28 bool operator <(const node &a)const 29 { 30 return val<a.val; 31 } 32 }; 33 int main() 34 { 35 int t; 36 scanf("%d",&t); 37 while(t--) 38 { 39 scanf("%d %d %d",&n,&m,&k); 40 int x; 41 for(int i=1;i<=n;i++) 42 a[i].clear(); 43 ans.clear(); 44 for(int i=1;i<=n;i++) 45 { 46 for(int j=1;j<=m;j++) 47 { 48 scanf("%d",&x); 49 a[i].push_back(x); 50 } 51 sort(a[i].begin(),a[i].end(),cmp); 52 } 53 priority_queue<node> q; 54 ans.push_back(0); 55 for(int i=1;i<=n;i++) 56 { 57 int x,y,z; 58 for(int j=0;j<m;j++) 59 { 60 z=a[i][j]+ans[0]; 61 q.push(node(0,j,z)); 62 } 63 while(d.size()<k&&!q.empty()) 64 { 65 node e=q.top();q.pop(); 66 d.push_back(e.val); 67 //printf("%d %d\n",cnt,d[cnt]); 68 //cnt++; 69 if(e.i+1<k&&i!=1) 70 q.push(node(e.i+1,e.j,ans[e.i+1]+a[i][e.j])); 71 } 72 while(!q.empty()) q.pop(); 73 ans.assign(d.begin(),d.end()); 74 d.clear(); 75 } 76 ll sum=0; 77 for(int i=0;i<k;i++) 78 sum+=ans[i]; 79 printf("%lld\n",sum); 80 } 81 }
原文：http://www.cnblogs.com/stranger-/p/7875446.html