给定m个序列，每个包含n个非负整数。

现在我们可以从每个序列中选择一个数字以形成具有m个整数的序列。

很明显，我们一共可以得到nmnm个这种序列， 然后我们可以计算每个序列中的数字之和，并得到nmnm个值。

现在请你求出这些序列和之中最小的n个值。

输入格式

第一行输入一个整数T，代表输入中包含测试用例的数量。

接下来输入T组测试用例。

对于每组测试用例，第一行输入两个整数m和n。

接下在m行输入m个整数序列，数列中的整数均不超过10000。

输出格式

对于每组测试用例，均以递增顺序输出最小的n个序列和，数值之间用空格隔开。

每组输出占一行。

数据范围

0<m≤10000<m≤1000,

0<n≤20000<n≤2000

输入样例：

12 31 2 32 2 3

输出样例：

3 3 4

 

 

算法：二叉堆（小根堆） + 数学归纳 + 贪心

题解：我们先看一下样例，可以分解为1+2 1+2 1+3 2+2 2+2 2+3 3+2 3+2 3+3这9个数，然后找出前3个最小的，答案自然就是3 3 4啦。

当m == 2时，我们先将数组a，b排序然后就可以得到这样一个序列和：

b[1]+a[1]   b[1]+a[2] ...... b[1]+a[n]

b[2]+a[1]   b[2]+a[2] ...... b[2]+a[n]

......

b[n]+a[1]   b[n]+a[2] ...... b[n]+a[n]

其中的序列和都是从小到大排序的，因为a和b数组都是有序的，所以我们只要将序列和的第一个都放入小根堆中，如果当前的第一个取出来了，我就把第二个放入小根堆中，依此类推。

注意：其中a数组中的每个元素都是前面几个序列和的最小的n个元素。

 

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const int maxn = 2e3+7;priority_queue
         
          
           , vector
           
            
              >, greater
             
              
                > > q;int n, m;int a[maxn], b[maxn], c[maxn];int main() { int T; scanf("%d", &T); while(T--) { scanf("%d %d", &m, &n); for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); } sort(a + 1, a + n + 1); for(int j = 2; j <= m; j++) { while(!q.empty()) { //清空上一次获取前n个最小的数之后的无用值 q.pop(); } for(int i = 1; i <= n; i++) { scanf("%d", &b[i]); } sort(b + 1, b + n + 1); for(int i = 1; i <= n; i++) { q.push(make_pair(a[1] + b[i], 1)); } for(int i = 1; i <= n; i++) { pair
               
                 v = q.top(); q.pop(); c[i] = v.first; q.push(make_pair(v.first + a[v.second + 1] - a[v.second], v.second + 1)); //这里是移动a数组的下标，上次用到了a[v.second],所以这次要减掉，加上新的值 } for(int i = 1; i <= n; i++) { //把更新后的最小数组赋值给a数组 a[i] = c[i]; } } for(int i = 1; i <= n; i++) { printf("%d%c", a[i], " \n"[i == n]); } } return 0;}