题目描述

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

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

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

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

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

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

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

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

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

每组输出占一行。

数据范围
$0<m≤1000$
$0<n≤2000$

样例

输入样例：
1
2 3
1 2 3
2 2 3
输出样例：
3 3 4

二叉堆+数学推导归纳

首先这道题目,我们可以先考虑N=2的这种特殊情况

我们发现,当A序列和B序列从小到大排序后,最小和肯定是A[1]+B[1],而次小和必然是min(A[2]+B[1],A[1]+B[2]),也就是说当我们确定好A[i][j]为K小和的话,那么第k+1小的和,必然是min(A[k+1]+B[k],A[k]+B[k+1]),既然如此的话,我们还要注意一点,A[1]+B[2]和A[2]+B[1]都可以推导出A[2]+B[2],所以说我们要记得,如果说j+1了,那么i就不要+1了,避免出现重叠,导致答案错误.至于min函数,可以使用小根堆来维护当前最小值.

数学的归纳法,我们就可以从2,推到N的情况,也就是先求出前两个序列的值,然后推出前N小的和的序列,然后用这个退出来的序列,再和第三个序列求值,然后同理,再得出来的值与第四个序列进行同样的操作.

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+10;
int a[N][N],now[N],n,m,t,i,j,k,ans[N];
struct node
{
    int x,y;
    bool ok;
};
bool operator < (node as,node bs)
{
    return a[k][as.y]+now[as.x]>a[k][bs.y]+now[bs.x];//权值比较
}
priority_queue<node>p,kong;
inline void init()
{
    cin>>m>>n;
    for(int i=1; i<=m; i++)
    {
        for(int j=1; j<=n; j++)
            cin>>a[i][j];
        sort(a[i]+1,a[i]+1+n);
        if (i==1)
            for(int j=1; j<=n; j++)
                now[j]=a[i][j];//设为第一个序列
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>t;
    while(t--)
    {
        init();
        i=1,j=1;
        for (k=2; k<=m; k++)//从第二个开始
        {
            p=kong;
            p.push(node {1,1,true});
            for (int km=1; km<=n; km++)
            {
                node pd=p.top();
                p.pop();//记得弹出堆顶
                ans[km]=now[pd.x]+a[k][pd.y];
                i=pd.x;
                j=pd.y;
                p.push(node {i,j+1,false});//第一种备选方案
                if (pd.ok==true)
                    p.push(node {i+1,j,true});//第二种备选方案
            }
            for (int km=1; km<=n; km++)
                now[km]=ans[km];
        }
        for (i=1; i<=n; i++)
            cout<<now[i]<<" ";
        cout<<endl;
    }
    return 0;
}