洛谷 - P1631 - 序列合并 - 堆

https://www.luogu.org/problemnew/show/P1631

序列a中每个数首先都和序列b中的最小元素配对（虽然好像不是很必要这么早插进来？）

每次从堆顶取出最小的和输出答案，然后尝试为这个ai配对下一个bj，要是没有的话……说明都是他一个人贡献完了。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;

int a[100005];

int b[100005];

struct Heap_Node{

    int val;

    //越小的val越大，所以比较的是val的相反数

    //这个node从属于u节点，当前匹配v节点

    int u,v;

    bool operator<(const Heap_Node& hn)const{

        return val>hn.val;

    }

    bool to_next_node(){

        //把v节点指向下一个位置

        if(v+1<=n){

            v++;

            val=a[u]+b[v];

            return true;

        }

        //这个节点已经没有用了

        return false;

    }

}hn;

priority_queue<Heap_Node> pq;

int main() {

#ifdef Yinku

    freopen("Yinku.in","r",stdin);

#endif // Yinku

    scanf("%d",&n);

    for(int i=1;i<=n;i++){

        scanf("%d",&a[i]);

    }

    for(int i=1;i<=n;i++){

        scanf("%d",&b[i]);

    }

    for(int i=1;i<=n;i++){

        hn.u=i;

        hn.v=1;

        hn.val=a[i]+b[1];

        pq.push(hn);

    }

    for(int i=1;i<=n;i++){

        hn=pq.top();

        pq.pop();

        printf("%d%c",hn.val," \n"[i==n]);

        if(hn.to_next_node())

            pq.push(hn);

    }

}