UVa 11997 - K Smallest Sums

#优先队列 #数据结构 #多路归并问题

Published on 2016-01-03

描述

有 $k(2\le k\le 750)$ 个数组，各包含 $k$ 个元素，在每个数组里都选出一个元素相加，可以得到 $k^{k}$ 个和，求这些和里中最小的 $k$ 个和？

样例输入

样例输出

9 10 12
2 2

附加输入

4
15 97 42 7
90 62 72 67
29 90 63 81
100 68 33 18
2
1054 14353
41752 94651
6
6 5 1 5 1 5
2 5 1 5 2 7
3 6 8 8 8 1
5 1 3 6 4 8
3 7 8 5 2 8
2 9 9 10 6 10
3
964 556 1182
4507 685 6878
7947 1836 4192
2
9353 4464
2747 4822
6
34 22 99 70 62 51
34 21 46 70 93 21
84 1 70 86 14 45
13 34 58 91 76 11
56 87 1 95 29 53
36 56 89 61 12 19
2
455 327
529 432
5
24248 21043 24805 22750 81271
43268 61167 98572 21473 35962
5270 64215 4224 80082 79742
13289 62033 99950 9019 48729
86510 86104 49975 61645 94096
5
2 7 7 8 4
7 9 9 7 3
10 5 2 9 5
3 7 10 9 1
7 9 8 7 6
4
8 1 1 8
7 8 6 2
1 3 3 4
2 9 4 1

附加输出

116 121 124 126
42806 56105
8 8 9 9 9 9
3077 3485 3703
7211 9286
68 68 70 70 75 75
759 856
105734 106780 107441 108487 108939
14 15 15 16 16
5 5 6 6

分析

直接全部算出来肯定爆炸，最多有 $750^{750}$ 种情况，瞬间超过宇宙中原子总数。我们得想想办法。
考虑这个问题的简化版本，有两个长度为 $n$ 的单调不递减数列 $A, B$ ，从中任取两个数加起来，求最小的 $n$ 个和是多少。我们建立 $n$ 个有序数列。
数列一： $A_{1} + B_{1} \le A_{1} + B_{2} \le A_{1} + B_{3} ... \le A_{1} + B_{n}$
数列二： $A_{2} + B_{1} \le A_{2} + B_{2} \le A_{2} + B_{3} ... \le A_{2} + B_{n}$
...
数列 $n$ ： $A_{3} + B_{1} \le A_{3} + B_{2} \le A_{3} + B_{3} ... \le A_{3} + B_{n}$
我打包票最小的一定是 $A_{1} + B_{1}$ ，但问题求最小的 $n$ 个和，那第二小的是谁呢？显然只可能存在于剩下的数列的第一个和以及数列一的第二个和中，我们可以知道，如果一个数列的前一个位置没有被选中，那么这个数列后面的数也不可能被选中。
所以我们建立一个优先队列（最小堆），一开始 push 进去所有数列的第一个数，如果某一个和出队，它一定是当前最小和。接着它所在的数列在它后面的一个和就要进队。第 $i$ 次出队得到第 $i$ 小的和，队列总是有 $n$ 个和，复杂度 $O(n\lg{n})$ 。这被称为多路归并问题。
那么这个题目也就不难解决了，根据贪心思想，将表两两合并，就能得到最小的 $k$ 个和。

代码

//  Created by Sengxian on 1/3/16.
//  Copyright (c) 2015年 Sengxian. All rights reserved.
//  UVa 11997 多路归并问题
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
const int maxn = 750 + 3;
int a[maxn], b[maxn], n;

bool eof = false;
inline int ReadInt() {
    int n = 0; char ch = getchar();
    while(ch < '0' || ch > '9') ch = getchar();
    do {
        n = n * 10 + ch - '0';
        ch = getchar();
    }while(ch <= '9' && ch >= '0');
    return n;
}

//计算出长度为 n 的数组 a，b 中最小的 n 个和存入数组 c
typedef pair<int, int> state;
void merge(int *a, int *b, int *c, int n) {
    priority_queue<state, vector<state>, greater<state> > pq;
    //表1：a1 + b1 <= a1 + b2
    //表2：a2 + b1 <= a2 + b2
    //表n：an + b1 <= an + bn
    for(int i = 0; i < n; ++i)
        pq.push(state(a[i] + b[0], 0));
    for(int i = 0; i < n; ++i) {
        state now = pq.top(); pq.pop();
        c[i] = now.first;
        if(now.second + 1 < n) pq.push(state(now.first - b[now.second] + b[now.second + 1], now.second + 1));
    }
}

int main() {
    while(~scanf("%d", &n) && n) {
        for(int i = 0; i < n; ++i)
            if(i == 0) {
                 for(int j = 0; j < n; ++j) a[j] = ReadInt();
                sort(a, a + n);
            }else {
                for(int j = 0; j < n; ++j) b[j] = ReadInt();
                sort(b, b + n);
                merge(a, b, a, n);
            }
        for(int i = 0; i < n; ++i)
            printf("%d%c", a[i], i + 1 == n ? '\n' : ' ');
    }        
    return 0;
}

UVa 246 - 10-20-30 UVa 10735 - Euler Circuit(混合图欧拉回路)

Sengxian's Blog