K个最小和 (UVA 11997 K Smallest Sums)

    Input

    There will be several test cases. The first line of each case contains an integer k (2<=k<=750). Each of the following k lines contains k positive integers in each array. Each of these integers does not exceed 1,000,000. The input is terminated by end-of-file (EOF). The size of input file does not exceed 5MB.

    Output

    For each test case, print the k smallest sums, in ascending order.

    Sample Input

    3
    1 8 5
    9 2 5
    10 7 6
    2
    1 1
    1 2

    Output for the Sample Input

    9 10 12
    2 2

    给定一个k*k的一个矩阵，如果让你在每一行取出一个数，再将每一行取出的数相加，那么总共可以得到k^k种相加方法，现在让你求出这k^k个结果中最小的k个结果。

    如果我们已经计算出了前m行，每行取出一个数相加的最小的k个结果，分别是DP[1],DP[2]…DP[k] (注意这里的DP表示的是前m行每行一个相加的最小的前k个值)

    假设第m+1行的值是A[1],A[2]…A[k] (注意这里的A[i]表示的是第m+1行的第i个数) 当我们推倒到第m+1行时，由于我们只计算了前m行的前k个最小值，那我们是不是有必要多计算一些来推导出第m+1行的前k个最小值呢？

    答案是不必要的，我们可以通过以下数学公式严格证明：
    设DP[x]是前m行通过计算得出的第x(x>k)小的和，如果上述的假设成立，那么我们可以列出不等式：

    上述不等式的含义是指在第m+1行存在一个数A[y],使得DP[x]+A[y]是前m+1行中前k小的结果。
    同时，我们注意到:

    2. A[y] >= A[1]           (3)

    由上面三个不等式(1),(2),(3)我们可以得到：

    1. （DP[1]+A[1]）,(DP[2]+A[1])...(DP[k-1]+A[1])共计k-1个，

    所以DP[k]+A[1]是第k个最小的和，与假设的DP[m]+A[n]是第k个最小的和相矛盾，所以假设不成立。得证。

    通过以上的证明我们可以得出结论要计算第m+1行的前k个最小和是只需要计算出前m行的前k个最小的和即可。这时，我们的目标就转化为了计算一个2*k的数组，在第一行取一个数，在第二行取一个数，得到k^2个和，求他们当中的最小的k个和。

    为了计算它，我们把这n^2个数组织成如下n个有序表：

    这时我们用一个二元组（sum， b）来保存以上的每一个元素，其中sum=A[a] + B[b].

    为什么不保存A的下标a呢？因为我们用不到a的值。如果我们需要在表(sum, b)中赵到下一个元素(sum’, b+1)，只要计算sum’ = s - B[b] + B[b+1],不需要知道a是多少。

    1. #include <cstdio>
    2. #include <algorithm>
    3. #include <queue>
    5. using namespace std;
    7. int  a[800][800],k;
    9. struct node
    10. {
    11.     int s,b;
    12.     {
    13.         return s>a.s;
    14.     }
    15. };
    18. {
    19.     node tmp;
    20.     priority_queue<node> q;
    21.     for(int i=0;i<n;i++)
    22.     {
    23.         tmp.s=A[i]+B[0],tmp.b=0;
    24.         q.push(tmp);
    25.     }
    26.     for(int i=0;i<n;i++)
    27.     {
    28.         tmp=q.top();
    29.         q.pop();
    30.         C[i]=tmp.s;
    31.         if(tmp.b+1<n)
    32.         {
    33.             tmp.b++;
    34.             q.push(tmp);
    35.         }
    37. }
    39. int main()
    40. {
    41.     while(~scanf("%d",&k))
    42.     {
    43.         for(int i=0;i<k;i++)
    44.         {
    45.             for(int j=0;j<k;j++)
    46.                 scanf("%d",&a[i][j]);
    47.             sort(a[i],a[i]+k);
    48.         }
    49.         for(int i=1;i<k;i++)
    50.             merge(a[0],a[i],a[0],k);
    51.         for(int i=0;i<k;i++)
    52.             printf("%d%s",a[0][i],i!=k-1?" ":"\n");
    53.     }
    54. }