Uva(11997)(K Smallest Sums)

链接：https://vjudge.net/problem/UVA-11997
思路：这虽然是一个优先队列的题，但其中的思想却远超过优先队列，原来是二个数组的，现在拓展成了n个。方法基本完全一样，首先我们要解决n行的前k个最小值，我们如果知道前n-1行的前k个值再加上最后一行就可以了，这样原问题可以拆分为子问题，然后在考虑状态更新之前我们先考虑一个问题，就是一行中第k个值最早被选也只能总的第k个值（因为他前k-1个都比他小），所以我们考虑到给每组和一个下标，是他最后更新的那个值在数组中的下标，用于确定前k个值是否选完。
说的不是很清楚，要靠自己领悟一下。。。。。
代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 768;
int A[maxn][maxn];

struct Item{
    int s,b;
    Item(){}
    Item(int ss,int bb):s(ss),b(bb){}
    bool operator<(const Item & r)const{
        return s>r.s;
    }
};

void merge(int* A,int *B,int* C,int n){
    priority_queue<Item> q;
    for(int i=0;i<n;i++)q.push(Item(A[i]+B[0],0));//合并第一排和第二排第一个值
        for(int i=0;i<n;i++){
            Item item = q.top();
            q.pop();
            C[i] = item.s;//记录当前第i小的值
            int b = item.b;
            if(b+1<n)q.push(Item(item.s-B[b]+B[b+1],b+1));//更新，将第二排下标后移一个
        }
}


int main(){
    int n;
    while(scanf("%d",&n)==1){
        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++)
            merge(A[0],A[i],A[0],n);//可以覆盖A[0]来记录结果，节约空间。
        printf("%d",A[0][0]);
        for(int i=1;i<n;i++)
            printf(" %d",A[0][i]);
        printf("\n");
    }
return 0;
}