题目描述
在一个n行m列的数阵中，你须在每一行取一个数（共n个数），并将它们相加得到一个和。对于给定的数阵，请你输出和前k小的取数方法。
解析
写这题完全自闭。
根本没联想起远古时期做的 P1631 序列合并 ，这题几乎是我刚入门做的了，代码还是仿的。
真的想了很久，怀疑自己智商.jpg。
首先如果做了 P1631 序列合并 而且还记得，那么这道题其实很好做。实际上就是把求两行的前(k)小和改成了求(n)行的前(k)小和。
两行的情况：设单调递增数列(a,b)，其存在最小值(a_1+b_1)，次小值为(min(a_2+b_1,a_1+b_2))。
推广到一般，对于第(k)小值(a_n+b_m)，我们有第(k+1)小值(min(a_n+b_{m+1},a_{n+1}+b_m))。
因此有算法，我们将(a_1+b_1)加入优先队列，不断扩展，每次可扩展出两个可行解，执行(k)次，所以显然也有最终答案下标一定不会超过(k)。
(n)行的情况，我们在行与行间进行迭代，应用与两行情况类似的算法。
换句话说，对于递增的行(x,y,z)，该算法就是先求(x,y)的前(k)小和，这些和组成新的数列，再跟(z)执行该算法，可以求出(x,y,z)三行的前(k)小和。
简单证明：
设(x,y)的前(k)小和构成的数列为(x')，(sum(i,j))表示从第(i,j)行分别任意取一个元素相加得到的新数列。如果(z)中有一元素(q)，其与一元素(pin sum(x,y))，且(p otin x')相加构成(sum(x',z))的第(k')小值，且(k'<k)。那么一定有一元素(p' in x')与(q)构成更优的第(k')小值，故这样的(p)不存在。即(sum(x',z)=sum(x,y,z))。也就是说这个迭代是没有问题的。
参考代码
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#define N 801
using namespace std;
inline int read()
{
int f=1,x=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
struct node{
int val,ap,bp;
bool operator<(const node &a)const{
return a.val<val;
}
node(){}
node(int _v,int _a,int _b){val=_v,ap=_a,bp=_b;}
};
priority_queue<node> q;
int a[N],b[N],n,m,k,t[N];
int main()
{
n=read(),m=read(),k=read();
for(int i=1;i<=m;++i) a[i]=read();
sort(a+1,a+m+1);
for(int i=2;i<=n;++i){
for(int j=1;j<=m;++j) b[j]=read();
sort(b+1,b+m+1);
while(q.size()) q.pop();//换成开个新的优先队列或许更快？
for(int j=1;j<=k;++j) q.push(node(a[j]+b[1],j,1));//小优化
for(int j=1;j<=k;++j){
node x=q.top();q.pop();
t[j]=x.val;
if(x.bp<m) q.push(node(a[x.ap]+b[x.bp+1],x.ap,x.bp+1));
}
memcpy(a,t,sizeof(a));//迭代
}
for(int i=1;i<=k;++i) printf("%d ",a[i]);
return 0;
}