首页 > 代码库 > K Smallest Sums

K Smallest Sums

2024-07-14 00:26:10   220人阅读

uva11997:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=24&problem=3148&mosmsg=Submission+received+with+ID+13942033

题意：给你k个数组，每个数组里有k个数，然后每个数组里面取出一个数相加会得到一个数，让你求出最小的看的数。

题解：白书的分析:

分析：这题有简化版本的，即2个整数数组A,B，包含K个元素，在每个数组中取一个元素加起来，可以得到k^2个和，求这些和中最小的K个值。

我们需要把这k^2个和组织成如下k个有序表.

表1：A1+B1<=A1+B2<=......<=A1+Bk

表2: A2+B1<=A2+B2<=......<=A2+Bk

表k：Ak+B1<=AK+B2<=......<=Ak+Bk

我们可以用二元组（s,b)来表示一个元素即s=Aa+Bb;为什么不保存A的下标a呢？因为我们用不到a的值。如果我们需要元素（s,b)在表a的下一个元素(s‘,b+1).只需要计算s‘=s+B[b+1]-B[b];

思想感觉就是DP。

 1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<queue> 6 using namespace std; 7 int a[800][800]; 8 int k; 9 int ans[800];10 struct Node{11    int s;12    int id;13    bool operator<(const Node a)const {14      return s>a.s;15    }16 };17 void merge(int a[],int b[]){18    priority_queue<Node>Q;19    for(int i=1;i<=k;i++){20     Node tt;21     tt.s=a[i]+b[1];22     tt.id=1;23     Q.push(tt);24    }25    for(int i=1;i<=k;i++){26       Node temp=Q.top();27       Q.pop();28       ans[i]=temp.s;29       Node t2;30       int num=temp.id;31       if(num<k){32         t2.s=temp.s-b[num]+b[num+1];33         t2.id=num+1;34       Q.push(t2);35       }36    }37 }38 int main(){39   while(~scanf("%d",&k)){40     memset(a,0,sizeof(a));41     memset(ans,0,sizeof(ans));42     for(int i=1;i<=k;i++){43         for(int j=1;j<=k;j++)44             scanf("%d",&a[i][j]);45         sort(a[i]+1,a[i]+k+1);46     }47      merge(a[1],a[2]);48     for(int i=3;i<=k;i++)49      merge(ans,a[i]);50      for(int i=1;i<k;i++)51         printf("%d ",ans[i]);52       printf("%d\n",ans[k]);53   }54 }
View Code

K Smallest Sums


联系
我们