POJ2442：Sequence

浅谈堆：https://www.cnblogs.com/AKMer/p/10284629.html

题目传送门：http://poj.org/problem?id=2442

我们先简化题意，假设只有两行。

那么显然，最小值是\(a_1+b_1\)。并且次小值集合是\(a_2+b_1,a_1+b_2\)。

假设\(a_1+b_2\)是次小值，那么次次小值集合就是\(a_2+b_1,a_2+b_2,a_1+b_3\)。

也就是说，当\(a_i+b_j\)成为当前最小值之后，\(a_{i+1}+b_j,a_i+b_{j+1}\)将会进入当前集合的次小值集合。我们用堆维护一下，每次取出最小值再把扩展出来的两个数扔回去就行了。

但是，\(a_2+b_2\)显然是可以通过\(a_1+b_2\)和\(a_2+b_1\)扩展出来的，如果不去重的话显然状态是非常非常多的，那样空间时间都没法保证。

所以我们强行勒令\(a_i+b_j\)只能转移到\(a_i+b_{j+1}\)，前提是\(a_i+b_j\)是由\(a_i+b_{j-1}\)扩展来的。

也就是说，假设现在有两个指针分别在第一行和第二行上移动，对于\(a_i+b_j\)必须满足\(i\)先移动\(j\)再移动然后到了这个地方。这样就不会有重复的状态了，也不会露掉中间值。

时间复杂度：\(O(mnlogn)\)

空间复杂度：\(O(n)\)

代码如下：

#include <cstdio>

#include <algorithm>

using namespace std;

const int maxn=2e3+5;

int n,m;

int num1[maxn],num2[maxn],tmp[maxn];

int read() {

	int x=0,f=1;char ch=getchar();

	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

	for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

	return x*f;

}

struct node {

	bool bo;

	int x,y;

	node() {}

	node(int _x,int _y,bool _bo) {

		x=_x,y=_y,bo=_bo;

	}

	bool operator<(const node &a)const {

		return num1[x]+num2[y]<num1[a.x]+num2[a.y];

	}

};

struct Heap {

	int tot;

	node tree[maxn];

	void ins(node v) {

		tree[++tot]=v;

		int pos=tot;

		while(pos>1) {

			if(tree[pos]<tree[pos>>1])

				swap(tree[pos],tree[pos>>1]),pos>>=1;

			else break;

		}

	}

	node pop() {

		node res=tree[1];

		tree[1]=tree[tot--];

		int pos=1,son=2;

		while(son<=tot) {

			if(son<tot&&tree[son|1]<tree[son])son|=1;

			if(tree[son]<tree[pos])

				swap(tree[son],tree[pos]),pos=son,son=pos<<1;

			else break;

		}

		return res;

	}

}T;

int main() {

	int TEST=read();

	while(TEST--) {

		m=read(),n=read();

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

			num1[i]=read();

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

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

			for(int j=1;j<=n;j++)

				num2[j]=read();

			sort(num2+1,num2+n+1);T.tot=0;

			int cnt=0;T.ins(node(1,1,0));

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

				node res=T.pop();

				tmp[++cnt]=num1[res.x]+num2[res.y];

				T.ins(node(res.x,res.y+1,1));

				if(!res.bo)T.ins(node(res.x+1,res.y,0));

			}

			for(int j=1;j<=n;j++)

				num1[j]=tmp[j];

		}

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

			printf("%d ",num1[i]);

		puts("");

	}

	return 0;

}