序列合并

· · 个人记录

题意概述：

$1.$暴力，考虑把所有 $N^2$ 个和加入堆中，求前 $N$ 个即可。时间复杂度 $O(N^2 \log N)$。 $2.$优化，注意到 $A_i,B_j$ 在这 $N$ 个和中当且仅当 $i \times j \le N$，否则我们可以找到替代 $A_k,A_l$（$k \le i,l<j$）。这样我们满足 $i \times j \le N$ 的只有 $O(N \ln N)$ 组，再加上优先队列一只 log，时间复杂度 $O(N \log^2 N)$。 对于本题数据范围已经可以过了，但如果 $N \le 10^6$ 呢？（思考题）。