uva 11997 K Smallest Sums

https://vjudge.net/problem/UVA-11997

题意：

给出k个数组，每个数组中有k个元素，要求从每个数组中选择一个元素相加得到的K^K个数中选择最小的k个并输出。

思路：

如果直接模拟，那么就是k^k的复杂度，显然是不能接受的。。。

首先看有两个数组的情况，先把A，B两个数组排序，把每一个A数组中的元素加B[0]  和    B[0]的下标     保存在一个结构体当中，扔进一个优先队列，

这个优先队列的优先级是sum小为队首（求的是最小值）。

之后从0到k - 1枚举，每次从优先队列中取一个元素，那么当前的sum肯定是最小的，于是记录，之后看看这个结构体保存的下标，如果小于K - 1的话，

那么就把sum - B[id].sum + B[id+1].sum和id+1丢进优先队列。这一步实际就保证了优先队列的队首始终是最小的元素并且元素不会重复加。

因为第一个比B[id].sum大的元素就是B[id+1].sum，所以sum - B[sum]实际是当前的A[i].sum，因为B[id].sum已经用过了，所以B[id+1].sum + A[i].sum进队就保证了当前队列中的k个元素一定是最小的。

那么K个数组，其实每次读入一个合并一次就好了。

这叫多路归并问题（不懂

具体还是结合代码理解，能手算理解一下更好！

代码：

#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std;

struct node
{
    long long sum;
    int b;

    bool operator < (const node& rhs) const
    {
        return rhs.sum < sum;
    }
};

node a[755],c[755];

int k;

void unit(void)
{
    priority_queue<node> pq;

    while (!pq.empty()) pq.pop();

    for (int i = 0;i < k;i++)
    {
        pq.push(node{a[i].sum + c[0].sum,0});
    }

    for (int i = 0;i < k;i++)
    {
        a[i].sum = pq.top().sum;
        int id = pq.top().b;

        pq.pop();

        if (id < k - 1)
        {
            pq.push(node{a[i].sum - c[id].sum + c[id+1].sum,id + 1});
        }

    }
}

bool cmp(node aa,node bb)
{
    return aa.sum < bb.sum;
}

int main()
{


    while (scanf("%d",&k) != EOF)
    {
        for (int i = 0;i < k;i++)
        {
            scanf("%lld",&a[i].sum);
        }

        for (int i = 1;i < k;i++)
        {
            for (int j = 0;j < k;j++)
            {
                scanf("%lld",&c[j].sum);
            }

            sort(a,a+k,cmp);
            sort(c,c+k,cmp);

            for (int j = 0;j < k;j++) c[j].b = j;

            unit();
        }

        sort(a,a+k);

        for (int i = k - 1;i >= 0;i--)
        {
            printf("%d%c",a[i].sum,i == 0 ? '
' : ' ');
        }
    }

    return 0;
}