SSOJ1475有序表的最小和
2719+
作者：crxis 发布：2020-06-15 分类：堆
题目大意：两个长度为n的数列，任意两数之和共有n*n个，最小的n个和是多少？
题目描述
给出两个长度为n的有序表A和B，在A和B中各任取一个元素，可以得到n2个和，求这些和中最小的n个。（不要去重）
输入
第一行包含一个整数n（n<=400000）; 第二行与第三行分别有n个整数，分别代表有序表A和B。整数之间由一个空格隔开，大小在长整型范围内，保证有序表的数据单调递增。
输出
输出共n行，每行一个整数，第i行为第i小的和。数据保证在长整型范围内。
样例输入
3
1 2 5
2 4 7
样例输出
3
4
5
解题思路
这n*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$，因为是有序表，所以每一行的和递增，也就是同一行，左边的和先输出，右边的和才有可能输出！
首先，我们可以先把第一列的和全部放入堆（优先队列），因为最小的肯定是这一列里面选。然后，没输出一个，就放入该元素对应行的下一个（列）元素！
因此，我们不仅需要记录元素的和，还要记录他是哪一行、哪一列。
n次操作，每次操作维护一个n个元素的堆，时间复杂度是$O(nlog_2n)$。
程序实现
手写堆：因为输出后，删除就马上插入一个新元素，所以不需要写插入的代码，只需要实现删除后从上往下维护即可。
