2021.07.02 UVa1197 多路归并模板

2021.07.02 UVa1197 多路归并模板

UVA11997 K Smallest Sums - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

分析：

题解 UVA11997 【K Smallest Sums】 - 一扶苏一 的博客 - 洛谷博客 (luogu.com.cn)

蓝书内容

代码如下：

//emmm……UVA，咱俩好好探讨一下毒瘤输出的问题

//多路归并模板

#include<cstdio>

#include<algorithm>

#include<iostream>

#include<queue>

using namespace std;

const int N=760;

int ans[N],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;

}

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

	priority_queue<node>q;

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

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

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

		c[i]=tmp.s;

		int bi=tmp.b;

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

	}

}

int main(){

	while(~scanf("%d",&n)){

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

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

		//for(int i=1;i<=n;i++)cout<<ans[i]<<" ";cout<<endl;//

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

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

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

			merge(ans,x,ans);

			//cout<<"ans ";

			//for(int j=1;j<=n;j++)cout<<ans[j]<<" ";cout<<endl;

		}

		//cout<<endl;//

		cout<<ans[1];

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

			cout<<" "<<ans[i];

		}

		cout<<endl;

	}

	return 0;

}

2021.07.02 UVa1197 多路归并模板的相关教程结束。