优先队列
n行每行n个数字 每行选一个求和 求和最小的n个
假设只有2行
每一行先排序
a1 a2 a3 ... an
b1 b2 b3 ... bn
把a1 + b1, a2 + b1, a3 + b1,..., an + b1入队列
然后取出一个最小的(pop ) 假如是ax + by 那么就放进去一个ax+b(y+1)(push)直到取出n个 把他们存到数组c
现在有n 那么可以两两合并 第一行和第二行合并后的结果在和第三行合并。。。。
#include <cstdio> #include <queue> #include <cstring> #include <algorithm> const int maxn = 800; using namespace std; int a[maxn][maxn]; struct Item { int s; int b; Item(int s, int b):s(s), b(b) {} bool operator < (const Item& rhs) const { return s > rhs.s; } }; int n; void merge(int* A, int* B, int* C) { 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 i, j; while(scanf("%d", &n) == 1) { for(i = 0; i < n; i++) { for(j = 0; j < n; j++) scanf("%d", &a[i][j]); sort(a[i], a[i]+n); } for(i = 1; i < n; i++) merge(a[0], a[i], a[0]); printf("%d",a[0][0]); for(i = 1; i < n; i++) printf(" %d", a[0][i]); printf("\n"); } return 0; }