pku2442.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 78 行

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define SIZE 2010
#define HEAP_MAX 1000000

using namespace std;

typedef struct Node
{
	int idx[100];
	int sum, start;
}Node;

int v[100][SIZE];
Node heap[HEAP_MAX];
int heap_size;
int m, n;

int cmp(const Node &a, const Node &b)
{
	return a.sum > b.sum;
}

void Solve()
{
	int i, j;
	int cnt, *p;
	scanf("%d%d", &m, &n);
	for (i = 0; i < m; i++)
	{
		for (j = 0; j < n; j++)
		{
			scanf("%d", v[i] + j);
		}
		sort(v[i], v[i] + n);
	}
	heap[0].sum = 0;
	for (i = 0; i < m; i++)
	{
		heap[0].idx[i] = 0;
		heap[0].sum += v[i][0];
		heap[0].start = 0;
	}
	heap_size = 1;
	p = heap[0].idx;
	cnt = 0;
	while (cnt < n)
	{
		printf("%d ", heap[0].sum);
		cnt++;
		for (i = heap[0].start; i < m; i++)
		{
			if (p[i] >= n - 1)
				continue;
			heap[heap_size] = heap[0];
			heap[heap_size].sum = heap[0].sum - v[i][p[i]] + v[i][p[i] + 1];
			heap[heap_size].idx[i]++;
			heap[heap_size].start = i;
			heap_size++;
			push_heap(heap, heap + heap_size, cmp);
		}
		pop_heap(heap, heap + heap_size, cmp);
		heap_size--;
	}
	printf("\n");
}

int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
		Solve();
	return 0;
}