当前位置:首页 > 数据结构 > > 正文
SSOJ1475有序表的最小和
206+

题目大意:两个长度为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)$。

程序实现

手写堆:因为输出后,删除就马上插入一个新元素,所以不需要写插入的代码,只需要实现删除后从上往下维护即可。

更多

About

坚决不Copy代码!

本文标签:,,,,,

SSOJ1475有序表的最小和:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter