题解 P1631 【序列合并】

· · 题解

最近有点忙 没时间贴代码了==

【分析】

首先,把A和B两个序列分别从小到大排序,变成两个有序队列。这样,从A和B中各任取一个数相加得到N2个和,可以把这些和看成形成了n个有序表/队列:

A[1]+B[1] <= A[1]+B[2] <= … <= A[1]+B[N]

A[2]+B[1] <= A[2]+B[2] <= … <= A[2]+B[N]

……

A[N]+B[1] <= A[N]+B[2] <= … <= A[N]+B[N]

接下来,就相当于要将这N个有序队列进行合并排序:

首先,将这N个队列中的第一个元素放入一个堆中;

然后;每次取出堆中的最小值。若这个最小值来自于第k个队列,那么,就将第k个队列的下一个元素放入堆中。

时间复杂度:O(NlogN)。

priority_queue<int, vector<int>,greater<int> > q;