传送门
首先，把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
上一篇：[luoguP1970] 花匠（DP）
下一篇：[codevs4655] 序列终结者（Splay）
stl 堆
