首页 > 代码库 > POJ 2442-Sequence（heap+k路归并）

POJ 2442-Sequence（heap+k路归并）

2024-07-21 23:54:47   217人阅读

Sequence
Time Limit: 6000MS Memory Limit: 65536K
Total Submissions: 7447 Accepted: 2451

Description

Given m sequences, each contains n non-negative integer. Now we may select one number from each sequence to form a sequence with m integers. It‘s clear that we may get n ^ m this kind of sequences. Then we can calculate the sum of numbers in each sequence, and get n ^ m values. What we need is the smallest n sums. Could you help us?

Input

The first line is an integer T, which shows the number of test cases, and then T test cases follow. The first line of each case contains two integers m, n (0 < m <= 100, 0 < n <= 2000). The following m lines indicate the m sequence respectively. No integer in the sequence is greater than 10000.

Output

For each test case, print a line with the smallest n sums in increasing order, which is separated by a space.

Sample Input

1
2 3
1 2 3
2 2 3

Sample Output

3 3 4
题意：给m个长度为n的数组，每次从每个数组中取一个数组成一个长度为m的数组（将数组中的数相加求和），操作n次，即取前n小和。
首先输入第一行（即第一个数组），升序排序，然后接下来输入m-1行，每次输入一行，将第一次输入的数组整体加上这次输入的第一个元素，然后维护成一个最大堆，再然后就要接着筛选，本质是继续维护这个最大堆，一直处理到输入结束即可。
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=2010;
int tem[maxn],ans[maxn],a[maxn];
int main()
{
    int t,n,m;
    scanf("%d",&t);
    while(t--)
	{
		scanf("%d%d",&m,&n);
		for(int i=0;i<n;i++)
			scanf("%d",ans+i);
		sort(ans,ans+n);
		for(int k=1;k<m;k++)
		{
			for(int i=0;i<n;i++)
			{
				scanf("%d",a+i);
				tem[i]=ans[i]+a[0];
			}
			make_heap(tem,tem+n);
			for(int i=1;i<n;i++)
				for(int j=0;j<n;j++)
			    {
				    int x=ans[j]+a[i];
				    if(x>=tem[0])break;
				    pop_heap(tem,tem+n);
				    tem[n-1]=x;
				    push_heap(tem,tem+n);
			    }
			    sort_heap(tem,tem+n);
			    for(int i=0;i<n;i++)
					ans[i]=tem[i];
		}
		for(int i=0;i<n;i++)
		    if(i!=n-1)
			printf("%d ",ans[i]);
		    else
			printf("%d\n",ans[i]);
	}
	return 0;
}


POJ 2442-Sequence（heap+k路归并）


联系
我们