首页 > 代码库 > POJ - 2442 Sequence

POJ - 2442 Sequence

2024-07-16 11:48:17   221人阅读

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个序列中每个选出一个，选出m个的和的最小的前n个

思路：跟UVA - 11997 K Smallest Sums思路是一样的

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 2005;

struct node {
	int s, b;
	node(int _s, int _b) {
		s = _s;
		b = _b;
	}
	bool operator <(const node &a) const {
		return s > a.s;
	}
};
int n, m;
int A[maxn][maxn];

void merge(int a[], int b[], int c[]) {
	priority_queue<node> q;
	for (int i = 0; i < n; i++)
		q.push(node(a[i]+b[0], 0));
	for (int i = 0; i < n; i++) {
		node cur = q.top();
		q.pop();
		c[i] = cur.s;
		int cnt = cur.b;
		if (cnt + 1 < n) 
			q.push(node(cur.s-b[cnt]+b[cnt+1], cnt+1));
	}
}

int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		scanf("%d%d", &m, &n);
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++)
				scanf("%d", &A[i][j]);
			sort(A[i], A[i]+n);
		}
		for (int i = 1; i < m; i++)
			merge(A[0], A[i], A[0]);
		printf("%d", A[0][0]);
		for (int i = 1; i < n; i++)
			printf(" %d", A[0][i]);
		printf("\n");
	}
	return 0;
}


联系
我们