UVA - 11997 K Smallest Sums

题意：有n个数组，各包含n个元素，在每个数组里任意选出一个元素加起来，可以得到n^n个和，求这些和里中最小的n个值

思路：将每个数组排序后，拿两个数组来说，会有例如：

A1+B1 <= A1+B2 < ...

A2+B1 <= A2+B2...

......

......

分析Aa+Bb,我们用二元组（s,b）来表示，其中s = Aa+Bb,可以推出

Aa+B(b+1) = Aa+Bb-Bb+B(b+1) = s + B(b+1) - Bb，采用优先队列，每次选出最小的，依次推

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

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 A[MAXN][MAXN],n;

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 temp = q.top();
        q.pop();
        C[i] = temp.s;
        int b = temp.b;
        if (b+1 < n)
            q.push(node(temp.s-B[b]+B[b+1],b+1));
    }
}

int main(){
    while (scanf("%d",&n) != EOF){
        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]);
        printf("%d",A[0][0]);
        for (int i = 1; i < n; i++)
            printf(" %d",A[0][i]);
        printf("\n");
    }
    return 0;
}

UVA - 11997 K Smallest Sums

原文：http://blog.csdn.net/u011345136/article/details/19366703