现在的位置: 首页 > 综合 > 正文

B(UVA-11997)k个最小和

2013年02月10日 ⁄ 综合 ⁄ 共 1618字 ⁄ 字号 评论关闭

Problem K

K Smallest Sums

You're given k arrays, each array has k integers. There are kk ways to pick exactly one element in each array and calculate the sum of the integers. Your task is to find the k smallest sums among them.

Input

There will be several test cases. The first line of each case contains an integer k (2<=k<=750). Each of the following k lines contains k positive integers in each array. Each of these integers does not exceed 1,000,000.
The input is terminated by end-of-file (EOF). The size of input file does not exceed 5MB.

Output

For each test case, print the k smallest sums, in ascending order.

Sample Input

3
1 8 5
9 2 5
10 7 6
2
1 1
1 2

Output for the Sample Input

9 10 12
2 2

Rujia Liu's Present 3: A Data Structure Contest Celebrating the 100th Anniversary of Tsinghua University
Special Thanks: Yiming Li
Note: Please make sure to test your program with the gift I/O files before submitting!

题目是一道经典的多路合并的题目,一直都没有注意一些细节,觉得自己懂了,就瞎写,今天换了一个环境,破釜沉舟吧,

加油。不谢的努力,你应该能够成功。

这个题目还是有个小模版的就是优先队列维护二路合并的最小和,

当然,k路合并,就是依次两路合并贪心过去。

真的比较不错,一会还得去找找多路合并的题目;

贴出代码:

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <string>
#include <queue>
#include <algorithm>

using namespace std;

int A[770][770];

int K;

struct Node
{
	int sum;
	int y;
	bool operator < (const Node& t) const
	{
		return sum > t.sum;
	}
}node;

void merge(int* a, int* b, int* c)
{
	priority_queue <Node> Q;
	for (int i = 0; i < K; i++)
	{
		node.sum = b[0] + a[i];
		node.y = 0;
		Q.push(node);
	}
	for (int i = 0; i < K; i++)
	{
		node = Q.top();
		Q.pop();
		c[i] = node.sum;
		int num = node.y;
		node.sum = node.sum - b[num] + b[num + 1];
		node.y = num + 1;
		if (num + 1 < K)
		{
			Q.push(node);
		}
	}	
}

int main()
{
	while (scanf("%d", &K) != EOF)
	{
		for (int i = 0; i < K; i++)
		{
			for (int j = 0; j < K; j++)
			{
				scanf("%d", &A[i][j]);
			}
			sort(A[i], A[i] + K);
		}
		for (int i = 1; i < K; i++)
		{
			merge(A[0], A[i], A[0]);
		}
		for (int i = 0; i < K; i++)
		{
			printf(i == K - 1 ? "%d\n" : "%d ", A[0][i]);
		}
	}
//	system("pause");
	return 0;
}

抱歉!评论已关闭.