题解 P1631 【序列合并】

csyakuoi · 2018-11-01 08:36:34 · 题解

有不用优先队列，代码不到30行的做法（P党福利）。

当i*j>n时，A_i+B_j一定不是前n小的数。

理由：因为两个序列均有序，所以如果x<=i而且y<=j那么A_x+B_y<A_i+B_j。于是至少有i*j个数小于等于A_i+B_j。 当i*j>n时，一定有多余n个数小于等于A_i+B_j，所以A_i+B_j一定不是前n小的数。

于是，我们可以枚举可能成为前n小的数的A_i+B_j，然后排序输出（P党不用手写优先队列拉）。