Sequence
| Time Limit: 6000MS | Memory Limit: 65536K | |
| Total Submissions: 7018 | Accepted: 2265 |
Description
Given m sequences, each contains n non-negative integer. Now we may select one number from each sequence to form a sequence with m integers. It's clear that we may get n ^ m this kind of sequences. Then we can calculate the sum of numbers in each sequence, and get n ^ m values. What we need is the smallest n sums. Could you help us?
Input
The first line is an integer T, which shows the number of test cases, and then T test cases follow. The first line of each case contains two integers m, n (0 < m <= 100, 0 < n <= 2000). The following m lines indicate the m sequence respectively. No integer in the sequence is greater than 10000.
Output
For each test case, print a line with the smallest n sums in increasing order, which is separated by a space.
Sample Input
12 31 2 32 2 3
Sample Output
3 3 4 思路： 1.s1[M] 表示第1组n个数，按递增排序。s2[M]表示第2组n个数，按递增排序 2.sum[i] = s2[0] + s1[i] i ∈ 0，1,2,3……n-1 并将sum[]数组建最大堆。这里我用优先队列实现 3.计算ans = s2[i] + s1[j] i ∈ 1,2,3……n-1, j ∈ 0，1,2,3……n-1 . 其中当i = 1时，j依次取j的范围，i = 2时，j依次取j的范围 …… 4.每次计算的 ans >= 堆顶 则退出此次，进行下一次，否则的话将堆顶删除将ans加到堆中。 5.将堆转换成s1数组，继续输入第三组到s2数组。重复上述步骤。 则最后堆里的内容就是最后要求的结果。
1 /*====================================================================== 2 * Author : kevin 3 * Filename : Sequence.cpp 4 * Creat time : 2014-07-23 09:27 5 * Description : 6 ========================================================================*/ 7 #include8 #include 9 #include 10 #include 11 #include 12 #include 13 #define clr(a,b) memset(a,b,sizeof(a))14 #define M 200515 using namespace std;16 int s1[M],s2[M],sum[M];17 priority_queue que;18 int main(int argc,char *argv[])19 {20 int cas;21 scanf("%d",&cas);22 while(cas--){23 int n,m;24 scanf("%d%d",&n,&m);25 for(int i = 0; i < m; i++){26 scanf("%d",&s1[i]);27 }28 sort(s1,s1+m);29 for(int i = 1; i < n; i++){30 for(int j = 0; j < m; j++){31 scanf("%d",&s2[j]);32 }33 sort(s2,s2+m);34 for(int j = 0; j < m; j++){35 sum[j] = s2[0] + s1[j];36 que.push(sum[j]);37 }38 int mmax = 0;39 for(int k = 1; k < m; k++){40 for(int j = 0; j < m; j++){41 mmax = s2[k] + s1[j];42 if(mmax >= que.top()) break;43 que.pop();44 que.push(mmax);45 }46 }47 int cnt = 0;48 while(!que.empty()){49 s1[cnt++] = que.top();50 que.pop();51 }52 sort(s1,s1+cnt);53 }54 for(int i = 0; i < m; i++){55 if(i)56 printf(" %d",s1[i]);57 else printf("%d",s1[i]);58 }59 printf("\n");60 }61 return 0;62 }