P1392 取数

题目描述 【#】

        在一个 n 行 m 列的数阵中，你须在每一行取一个数（共 n 个数），并将它们相加得到一个和。对于给定的数阵，请你输出和前 k 小的取数方法。

思路

        · 先缩小思考范围，仅考虑n=2的情况

         · 每行可自行增序排序

        · 枚举第1,2,3,…,k小的数，第1小由a11+a21开始

        · 若第k小为a1i+a2j，则a1i+1+a2j、a1i+a2j+1要纳入第k+1小的考虑行列

        · 显然待考虑项可用堆维护 考虑由i行扩展至i+1行， 先求出前i行的最小k项和，维护第i+1行与其组合的前k值即可 （from TD）

        先对一二两行进行处理，取前k小的数，再与下一行运算       用优先队列实现

#include<bits/stdc++.h>
using namespace std;
int n,m,k,a[805],b[805],c[805];
struct node{
	int x,a,b;
	bool operator<(const node &y) const
	{ return x>y.x; }
};
priority_queue<node> q;
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=m;i++) scanf("%d",&a[i]);
	sort(a+1,a+1+m);
	for(int i=2;i<=n;i++)
	{
		for(int j=1;j<=m;j++) scanf("%d",b+j); sort(b+1,b+1+m);
		while(!q.empty()) 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(); c[j]=x.x;
			if(x.b<m) q.push((node){a[x.a]+b[x.b+1],x.a,x.b+1});
		}
		for(int j=1;j<=k;j++) a[j]=c[j];
	}
	for(int i=1;i<=k;i++) cout<<a[i]<<" ";
	return 0;
}