习题整理——优先队列UVA11997

UVA 11997

思路：

先考虑两组数，各取其中一个，组成前k个最小的树

a = {a1, a2, a3, a4},    b = {b1, b2, b3, b4}，a和b已经全部从小到大排好序

如果有3组数，第三组为：c = {c1, c2, c3, c4}，假设上边前4个最小的组合构建为 ab = {a1+b1, a1+b2, a2+b1, a2+b2}，那么对于ab和c两个数组做同样的操作，得出前k个最小的组合就是三组数中的最小组合。

有n组数也是同理。

以{1，5，8； 2，5，9； 6，7，10}为例。

空数组 temp，现在处理的是前两组数{1,5,8; 2,5,9}

优先队列 q = {1+2, 5+2, 8+2}, 弹出最小值放入temp，temp={3}，压入1+5，

q = {1+5,5+2,8+2},弹出，temp = {3,6}, 压入1+9

q = {5+2, 8+2, 1+9}, 弹出，temp = {3, 6, 7}，结束第一轮

空数组temp1，现在处理的是temp和{6,7,10}

优先队列q = {3+6，6+6，7+6}, 弹出，temp1 = {9},压入3+7

q = {3+7,6+6,7+6},弹出，temp1 = {9,10},压入3+10

q = {6+6,6+7,3+10}，弹出，temp1 = {9, 10,12}，结束

代码：

#include<iostream>
#include<math.h>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
typedef struct Node{
    int s;
    int a;//a是第一个数的位置
    int b;//b是第二个数的位置
          //比如a1+b2,a就记录了1，b就记录了2
    Node(int aa,int bb,int ss){
        a = aa;
        b = bb;
        s = ss;
    }
    bool operator < (const Node a) const{
        return s>=a.s;//小顶堆
    }
}Node;
int main(){
    int k;
    while(cin>>k){
        int number[k][k];//k组数记录在number[k][k]中
        int best_k[k][k];//best_k记录每次两个数组的前k个最小组合
        for(int i=0;i<k;i++){
            for(int j=0;j<k;j++)
                cin>>number[i][j];
            sort(number[i],number[i]+k);//对每组数排序
        }
        for(int i=0;i<k;i++)
            best_k[0][i] = number[0][i];
        for(int l=1;l<k;l++){
            priority_queue<Node> q;
            for(int i=0;i<k;i++)
                //将a1+b1,a2+b1,a3+b1......入队
                q.emplace(i,0,best_k[l-1][i]+number[l][0]);
            for(int i=0;i<k;i++){
                Node t = q.top();
                q.pop();
                best_k[l][i] = t.s;
                //emplace功能push相同，里边的参数是构造新的Node的参数
                q.emplace(t.a,t.b+1,best_k[l-1][t.a]+number[l][t.b+1]);
                //t.b+1代表b向后移一个，例如从a1+b1变为a1+b2
            }
        }
        for(int i=0;i<k;i++){
            if(i!=0)
                cout<<' ';
            cout<<best_k[k-1][i];
        }
        cout<<endl;
    }
    return 0;
}