SSOJ2064第k小数2
5440+
作者：crxis 发布：2017-10-05 分类：单调队列
题目大意：两个单调递增的数组，他们之中第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小的是谁。
程序实现
