题意:
有k个整数数组,各包含k个元素。在每个数组中取一个元素加起来,可以得到k^k个和。求这些和中最小的前k个值(重复的值算多次)。
分析:
训练指南上的,很难想到的思路。
code:
#include <cstdio> #include <cstring> #include <algorithm> #include <queue> using namespace std; const int maxn = 768; int A[maxn][maxn]; struct Item { int s, b; Item(int s, int b):s(s),b(b){} bool operator < (const Item & t) const {return s > t.s;} }; void merge(int* A, int* B, int* C, int n) { priority_queue<Item> q; for(int i=0; i<n; i++) q.push(Item(A[i]+B[0], 0)); for(int i=0; i<n; i++) { Item item = q.top(); q.pop(); C[i] = item.s; int b = item.b; if(b+1<n) q.push(Item(item.s-B[b]+B[b+1], b+1)); } } int main() { int n; while(scanf("%d", &n)==1) { for(int i=0; i<n; i++) { for(int j=0; j<n; j++) scanf("%d",&A[i][j]); sort(A[i], A[i]+n); } for(int i=1; i<n; i++) merge(A[0], A[i], A[0], n); printf("%d",A[0][0]); for(int i=1; i<n; i++) printf(" %d",A[0][i]); printf("\n"); } return 0; }