一、前言

本题是贪心中的一种题型 堆优化贪心 的一种模型，本文将介绍其 证明 与 实现。

二、题意

有三行序列，每次都要从每一行中选一个数，将所选的三个数相加，得到一个新数。如此操作，输出所得的前 $K$ 大的数。

三、思路

既然要选前 $K$ 大的数，我们先将三个序列从大到小排序，那么显然最大的显然是 $a_1+b_1+c_1$。那么第二大的呢？我们有三个选择：$a_2+b_1+c_1$ 、 $a_1+b_2+c_1$ 与 $a_1+b_1+c_2$，不可能有其他选择。

证明：

显然。首先三个序列都是从大到小排列的，排在越前的数显然越大。$a_1,b_1,c_1$ 都是最大值，想要获得三个数的和的次小值肯定是 将一个最大值变成次大值，不可能将两个最大值变为次大值。假设修改两个数，即 $a_2+b_2+c_1$， 其一定不可能是次大值，因为一定有

$a_2+b_1+c_1$ 一定比它更有可能是次大值。因此得证。

之后每次都面临相同的选择，因此我们考虑将它们都丢进 大根堆 里。若当前队首为 $a_i+b_j+c_k$，就把 $a_{i+1}+b_j+c_k$、$a_i+b_{j+1}+c_k$、 $a_i+b_j+c_{k+1}$ 都丢进堆里，$k$ 次操作后的队首就是第 $k$ 小的情况。

还要考虑到 重复 的情况。$a_{i-1}+b_j+c_k$ 会产生 $a_i+b_j+c_k$，$a_i+b_{j-1}+c_k$ 和 $a_i+b_j+c_{k-1}$ 也会产生 $a_i+b_j+c_k$，$a_i+b_j+c_k$ 会重复出现，这是我们不愿意看到的。因此我们要考虑 去重。我是用 map 来做的，不知道有没有别的方法。

四、代码

#include<bits/stdc++.h>
#define ri register int
using namespace std;
typedef long long ll;

const int N=1e3+7;
int x,y,z,k;
ll a[N],b[N],c[N];
struct node
{
	int x,y,z;
	
	bool operator < (const node &oth) const
	{
		return a[x]+b[y]+c[z]<a[oth.x]+b[oth.y]+c[oth.z];
	}//重载运算符
};
priority_queue<node>q;//大根堆
map<pair<pair<int,int>,int>,bool>mp;//标记

bool cmp(ll a,ll b)
{
	return a>b;
}

inline ll read()
{
	ll sum=0,ff=1;
	char ch=getchar();
	while(!isdigit(ch))
	{
		if(ch=='-')
			ff=-1;
		ch=getchar();
	}
	while(isdigit(ch))
		sum=sum*10+(ch^48),ch=getchar();
	return sum*ff;
}

int main()
{
	x=read(),y=read(),z=read(),k=read();
	for(ri i=1;i<=x;i++)
		a[i]=read();
	for(ri i=1;i<=y;i++)
		b[i]=read();
	for(ri i=1;i<=z;i++)
		c[i]=read();
	
	sort(a+1,a+1+x,cmp);
	sort(b+1,b+1+y,cmp);
	sort(c+1,c+1+z,cmp);
	
	q.push((node){1,1,1});
	mp[make_pair(make_pair(1,1),1)]=true;
	
	for(ri i=1;i<=k;i++)
	{
		node now=q.top();
		q.pop();
		printf("%lld\n",a[now.x]+b[now.y]+c[now.z]);
		
		if(!mp.count(make_pair(make_pair(now.x+1,now.y),now.z))&&now.x<x)
		{
			mp[make_pair(make_pair(now.x+1,now.y),now.z)]=true;
			q.push((node){now.x+1,now.y,now.z});
		}
		if(!mp.count(make_pair(make_pair(now.x,now.y+1),now.z))&&now.y<y)
		{
			mp[make_pair(make_pair(now.x,now.y+1),now.z)]=true;
			q.push((node){now.x,now.y+1,now.z});
		}
		if(!mp.count(make_pair(make_pair(now.x,now.y),now.z+1))&&now.z<z)
		{
			mp[make_pair(make_pair(now.x,now.y),now.z+1)]=true;
			q.push((node){now.x,now.y,now.z+1});
		}
	}

	return 0;
}