题目链接： https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1136
分析见《算法竞赛入门经典-训练指南》P190
1 #include <iostream> 2 #include <algorithm> 3 #include <map> 4 #include <vector> 5 #include <functional> 6 #include <string> 7 #include <cstring> 8 #include <queue> 9 #include <set> 10 #include <cmath> 11 #include <cstdio> 12 13 14 using namespace std; 15 #define IOS ios_base::sync_with_stdio(false) 16 typedef long long LL; 17 const int INF = 0x3f3f3f3f; 18 const double PI=4.0*atan(1.0); 19 20 const int maxn=800; 21 typedef struct Item{ 22 int s,b; 23 Item(int s,int b):s(s),b(b){} 24 bool operator<(const Item &a) const{ 25 return s>a.s; 26 } 27 }I; 28 int k,a[maxn],b[maxn]; 29 void merge(int *a,int *b,int *c) 30 { 31 sort(a,a+k); 32 sort(b,b+k); 33 priority_queue<I> que; 34 for(int i=0;i<k;i++) 35 que.push(I(a[i]+b[0],0)); 36 for(int i=0;i<k;i++){ 37 I it=que.top(); que.pop(); 38 c[i]=it.s; 39 if(it.b<k-1) que.push(I(it.s-b[it.b]+b[it.b+1],it.b+1)); 40 } 41 } 42 int main() 43 { 44 while(scanf("%d",&k)!=EOF){ 45 for(int i=0;i<k;i++) scanf("%d",&a[i]); 46 for(int i=0;i<k-1;i++){ 47 for(int j=0;j<k;j++) scanf("%d",&b[j]); 48 merge(a,b,a); 49 } 50 for(int i=0;i<k-1;i++) printf("%d ",a[i]); 51 printf("%d ",a[k-1]); 52 } 53 }