POJ 2442 Sequence （堆）

POJ 2442 Sequence （堆）

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

题意

给出m组数，每组n个，求从每一组挑选出一个数相加产生前n小的和。

思路

假设只有一组数，那么前n小的和便是这组的所有元素，如果增加一组数之后，只有原来组的前n小的和才会对新组产生贡献（因为其他数相加产生的和一定不会是结果所说的前n个里面的），于是用一个二重循环来枚举计算添加完这一组之后的前n小的和。

AC 代码

#include#include#include#include#include#includeusing namespace std;#include#include

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。