UVA 11997 - K Smallest Sums（多路歸并）

題目連結：點選打開連結

思路：多路歸并。 用貪心的規則， 我們先考慮兩個數組的情況， 如果将兩個數組從小到大排序， 那麼我們先将數組a的所有元素加上數組b的最小的元素， 然後放入優先隊列。 因為是事先排好序的， 是以其中肯定有一個是最小的，那麼當這個數取出來之後， 如何保證隊列頭上時次小的呢？ 我們發現， a數組的所有元素都用上了， 而且是和b數組中最小的數相加得到的， 是以， 當a[0]+b[0]被取出， 下一個可能有用的和一定不是a[1]+b[0]， 因為已經在隊列中了， 那麼隻能是a[0] + b[1]。 貪心的每次取出一個數之後再加進去一個盡量小的值。

本題進行k次就行了。

細節參見代碼：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <bitset>
#include <cstdlib>
#include <cmath>
#include <set>
#include <list>
#include <deque>
#include <map>
#include <queue>
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
typedef long double ld;
const ld eps = 1e-9, PI = 3.1415926535897932384626433832795;
const int mod = 1000000000 + 7;
const int INF = 0x3f3f3f3f;
// & 0x7FFFFFFF
const int seed = 131;
const ll INF64 = ll(1e18);
const int maxn = 1000;
int T,n,m,a[maxn][maxn];
struct node {
    int s, b;
    node(int s=0, int b=0):s(s), b(b) {}
    bool operator < (const node& rhs) const {
        return s > rhs.s;
    }
};
void bin(int* a, int *b, int *c, int n) {
    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 cur = q.top(); q.pop();
        c[i] = cur.s;
        int id = cur.b;
        if(id+1 < n) q.push(node(cur.s-b[id]+b[id+1], id+1));
    }
}
int main() {
    while(~scanf("%d",&n)) {
        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++) {
            bin(a[0], a[i], a[0], n);
        }
        for(int i = 0; i < n; i++) {
            printf("%d%c", a[0][i], i == n-1 ? '\n' : ' ');
        }
    }
    return 0;
}