当前位置:首页 > 单调队列 > 正文
SSOJ2064第k小数2
4151+

题目大意:两个单调递增的数组,他们之中第k小的数是多少?

【问题描述】

“哇,好多冰淇淋啊!”张琪曼拉着李旭琳又跑到学院的冷饮店,问:“老板,这次你要第K小的魔法石?”老板笑着说:“我要……,咦,你们事先把魔法石都排好了?那可不行,这不赖皮嘛,我要改下规则。”

老板的新规则是:对于两个有序数组a[n]和a[m](1<n,m<100000),找出第k小的数。

【输入格式】

第一行三个整数n,m,k。

第二行是第一个有序数组的n个元素。

第三行是第二个有序数组的m个元素。

【输出格式】

第k小的数在数组中的位置。

【输入样例】

6 7 6

786 3891 4258 4694 7130 7899

357 720 1292 2579 7889 9255 9611

【输出样例】

3891

解题思路

将这n+m个数放到一个数组,从小打到排序后输出第k个即使答案,这样时间复杂度为O((m+n)log2(m+n)),利用单调队列的特性,复杂度可以降到O(m+n)。逐个找,先找最小,再找次小,一直找到第k小。因为原来是两个有序的单调递增的数组,每次只需要比较他们的开头,就可以确定第i小的是谁。

程序实现

About

坚决不Copy代码!

本文标签:,

SSOJ2064第k小数2:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!