【文件属性】：
文件名称：17082 两个有序数序列中找第k小
文件大小：1KB
文件格式：CPP
更新时间：2018-05-30 11:09:09
第k小
17082 两个有序数序列中找第k小（必做）
时间限制:1000MS 内存限制:65535K
提交次数:0 通过次数:0
题型: 编程题 语言: C++;C;VC;JAVA
Description
已知两个已经排好序（非减序）的序列X和Y，其中X的长度为m，Y长度为n，
现在请你用分治算法，找出X和Y的第k小的数，算法时间复杂度为O(max{logm, logn})。
此题请勿采用将序列X和Y合并找第k小的O(m+n)的一般方法，要充分利用X和Y已经排好序的这一特性。
输入格式
第一行有三个数，分别是长度m、长度n和k，中间空格相连（1<=m,n<=100000; 1<=k<=m+n）。
第二行m个数分别是非减序的序列X。第三行n个数分别是非减序的序列Y。
输出格式
序列X和Y的第k小的数。
输入样例
5 6 7
1 8 12 12 21
4 12 20 22 26 31
输出样例
20
提示
作者
zhengchan