UVA - 11997（巧妙的优先队列）

题意：

　　有k个整数数组，各包含k个元素，在每个数组中取一个元素加起来，可以得到k个和，求这些和中最小的k个值

解析：

　　从简单的情况开始分析：经典方法，对原题没有思路，那么分析问题的简化版

这是对于两个。。。而对于k个 我们只需要两两处理合并出新数组 然后再与另一个数组合并处理。。依次推理

#include <iostream>

#include <cstdio>

#include <sstream>

#include <cstring>

#include <map>

#include <set>

#include <vector>

#include <stack>

#include <queue>

#include <algorithm>

#include <cmath>

#define rap(i, a, n) for(int i=a; i<=n; i++)

#define MOD 2018

#define LL long long

#define ULL unsigned long long

#define Pair pair<int, int>

#define mem(a, b) memset(a, b, sizeof(a))

#define _  ios_base::sync_with_stdio(0),cin.tie(0)

//freopen("1.txt", "r", stdin);

using namespace std;

const int maxn = , INF = 0x7fffffff;

int A[maxn][maxn];

struct node

{

    int s, b;

    node(int s, int b):s(s), b(b){}

    bool operator < (const node& a) const {

        return s > a.s;

    }

};

void mer(int* A, int* B, int* C, int n)

{

    priority_queue<node> q;

    rap(i, , n)

        q.push(node(A[i]+B[], ));

    rap(i, , n)

    {

        node e = q.top(); q.pop();

        C[i] = e.s;

        int b = e.b;

        if(b +  <= n)

        {

            e.s = e.s - B[b] + B[b+];

            q.push(node(e.s, b+));

        }

    }

}

int main()

{

    int n;

    while(cin>> n)

    {

        rap(i, , n)

        {

            rap(j, , n)

                cin>> A[i][j];

            sort(A[i]+, A[i]+n+);

        }

        rap(i, , n)　　　　//两两合并

         mer(A[], A[i], A[], n);

        rap(i, , n)

        {

            if(i != )

                cout<< " ";

            cout<< A[][i];

        }

        cout<< endl;

    }

    return ;

}