2021.11.04 P1392 取数（多路归并)

2021.11.04 P1392 取数（多路归并)

P1392 取数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题意：

在一个n行m列的数阵中，你须在每一行取一个数（共n个数），并将它们相加得到一个和。对于给定的数阵，请你输出和前k小的数字和（这里是个自个儿造的专属名词）。

分析：

1到i-1行的前k个答案一定在与第i行合并后形成新的k个答案，毕竟两个最大的相加永远比不过两个最小的相加。

代码如下：

#include<cstdio>

#include<algorithm>

#include<iostream>

#include<cstring>

#include<queue>

using namespace std;

const int N=810;

int n,m,k,ans[N],x[N];

struct node{

	int s,b;

	bool operator <(const node &b)const{

		return s>b.s;

	}

};

inline int read(){

	int s=0,w=1;

	char ch=getchar();

	while(ch<'0'||ch>'9'){

		if(ch=='-')w=-1;

		ch=getchar();

	}

	while(ch<='9'&&ch>='0'){

		s=s*10+ch-'0';

		ch=getchar();

	}

	return s*w;

}

inline void merge(int *a,int *b,int *c){

	priority_queue<node>q;

	for(int i=1;i<=m;i++)q.push({a[i]+b[1],1});

	for(int i=1;i<=m;i++){

		node tmp=q.top();q.pop();

		c[i]=tmp.s;

		int bi=tmp.b;

		if(bi+1<=m)q.push({tmp.s-b[bi]+b[bi+1],bi+1});

	}

}

int main(){

	n=read();m=read();k=read();

	for(int i=1;i<=m;i++)ans[i]=read();

	sort(ans+1,ans+m+1);

	for(int i=2;i<=n;i++){

		for(int j=1;j<=m;j++)x[j]=read();

		sort(x+1,x+m+1);

		merge(ans,x,ans);

	}

	for(int i=1;i<=k;i++)cout<<ans[i]<<" ";

	return 0;

}

2021.11.04 P1392 取数（多路归并)的相关教程结束。