POJ 2442 Sequence堆优先队列

题目描述
给定m个序列，每个序列包含n个非负整数。现在我们可以从每个序列中选择一个数字以形成一个具有m个整数的序列。显然，我们可以得到n ^ m种这种序列。然后，我们可以计算每个序列中的数字总和，并获得n ^ m个值。我们需要的是最小的n个和。你可以帮我们吗？

题目大意：给定M个长度为N的序列，从每个序列中任意取一个数求和，可以构成N的M次方个和，求其中最小的N个和。

输入格式
第一行是整数T，它显示测试用例的数量，然后是T个测试用例。每种情况的第一行都包含两个整数m，n（0 <m <= 100，0 <n <= 2000）。以下m行分别表示m序列。序列中没有整数大于10000。

输出格式
对于每个测试用例，按升序打印具有最小n个和的行，并用空格隔开。

样例
样例输入
1
2 3
1 2 3
2 2 3
样例输出
3 3 4
数据范围与提示
POJ月刊，广林
题目分析
1.因为要求是打印前n小的，所以，我们可以给每一个序列先排个序
这样我们就可以累加每一个序列的首位，这个就是第一小的数，然后
我们就要找到第二小的
2.如果我们假设m=2;,则第二小的数在(a[2]+b[1)(a[1]+b[2])中，如果选择(a[2]+b[1])那么，第三小的在(a[3]+b[1]),(a[2]+b[2])(a[1]+b[2])中，。。。。
如果选择(a[k]+b[l],那么后面一小的在a[k+1]+b[l],a[k][l+1],与前面的剩余部分
最后求出以个长度n的序列，a,b便和并了，以同样的道理，和并一共m-1次
3.所以，我们可以建立一个小根堆，放入每一个要选择的和，每一次去取树根
4因为有重复的可能所以要用以个bool数组用巧妙的方法限制

#include<bits/stdc++.h>

using namespace std;

int Heap_size;

int n,m,T;

int a[2005],b[2005],c[2005];

struct ss{

	int st1,st2,zs,pd;

}Heap[2005],st,aa;

void Put_heap(ss x)

{

	Heap[++Heap_size]=x;

	int now=Heap_size;

	while(now>1&&Heap[now].zs<Heap[now>>1].zs)

	{

		swap(Heap[now],Heap[now>>1]);

		now>>=1;

	}

}

void Get_heap()

{

	Heap[1]=Heap[Heap_size--];

	int fa=1;

	while(fa<=Heap_size/2)

	{

		int son=fa*2;

		if(Heap_size>son&&Heap[son].zs>Heap[son+1].zs)

		{

			son++;

		}

		if(Heap[fa].zs>Heap[son].zs)

		{

			swap(Heap[fa],Heap[son]);

		}

		else

		{

			break;

		}

		fa=son;

	}

}

int main()

{

	scanf("%d",&T);

	while(T--)

	{

		scanf("%d %d",&m,&n);

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

		{

			scanf("%d",&a[i]);

		}

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

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

		{

			Heap_size=0;

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

			{

				scanf("%d",&b[j]);

			}

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

			st.st1=1;

			st.st2=1;

			st.pd=0;

			st.zs=a[1]+b[1];

			Put_heap(st);

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

			{

				st=Heap[1];

				Get_heap();

				c[j]=st.zs;

				if(!st.pd)

				{

					aa.st1=st.st1+1;

					aa.st2=st.st2;

					aa.pd=0;

					aa.zs=a[aa.st1]+b[aa.st2];

					Put_heap(aa);

					aa.st1=st.st1;

					aa.st2=st.st2+1;

					aa.zs=a[aa.st1]+b[aa.st2];

					aa.pd=1;

					Put_heap(aa);

				}

				else

				{

					aa.st1=st.st1;

					aa.st2=st.st2+1;

					aa.pd=1;

					aa.zs=a[aa.st1]+b[aa.st2];

					Put_heap(aa);

				}

			}

			for(int j=1;j<=n;j++) a[j]=c[j];

		}

		for(int i=1;i<=n;i++) printf("%d ",a[i]);

		printf("\n");

	}

 }

巴特西

POJ 2442 Sequence堆优先队列

最新文章

热门文章

巴特西

POJ 2442 Sequence堆 优先队列

最新文章

热门文章

POJ 2442 Sequence堆优先队列