首页 > 代码库 > poj 2442 -- Sequence

poj 2442 -- Sequence

2024-07-13 15:21:59   219人阅读

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 #include <iostream> 8 #include <algorithm> 9 #include <cstdio>10 #include <cstring>11 #include <queue>12 #include <cmath>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<int>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 }
View Code


联系
我们