[luoguP1631] 序列合并（堆 || 优先队列）

传送门

首先，把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)。

——代码

1 #include <queue> 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 #include <algorithm> 6 7 const int MAXN = 100001; 8 int n; 9 int a[MAXN], b[MAXN]; 10 11 struct node 12 15 }; 16 17 inline bool operator < (const node v1, const node v2) 18 21 22 std::priority_queue <node> q; 23 24 inline int read() 25 32 33 int main() 34 48 return 0; 49 }
View Code

上一篇：[luoguP2896] [USACO08FEB]一起吃饭Eating Together（DP）

下一篇：[luoguP2280] [HNOI2003]激光炸弹（DP）

---

stl 堆