17082 两个有序数序列中找第k小（必做）
时间限制:1000MS 内存限制:65535K 提交次数:0 通过次数:0
题型: 编程题 语言: G++;GCC;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。
1 #include <stdio.h> 2 #include <stdlib.h> 3 #define maxn 100010 4 int a[maxn],b[maxn],k; 5 6 int f(int la,int ra,int lb,int rb)//类似2分法 7 { 8 int halflen, ma, mb; 9 if(lb > rb) return a[la+k-1];//递归边界 10 if(la > ra) return b[lb+k-1];//递归边界 11 ma=(ra + la) / 2; 12 mb=(rb + lb) / 2; 13 halflen = ma - la + mb - lb + 2;//两个数组左边的数量 14 if(a[ma] < b[mb]) 15 { //如果左边的数量还是比k大，则第k小的在两个数组的左边，而且第k大的坑定比b[mb]小 16 //则将b数组的右边去掉，在进行递归 17 if(k < halflen) return f(la, ra, lb, mb-1); 18 //如果左边的数量还是比k小，则第k小的在两个数组的右边，而且第k大的坑定比a[ma]大 19 //则将a数组的左边去掉，在进行递归，递归之前，要把k更新，不在是第k小了，而是 20 //k - (ma - la + 1); 21 k = k - (ma - la + 1); 22 return f(ma+1, ra, lb, rb); 23 } 24 else 25 { 26 27 //同上 28 if(k < halflen) return f(la, ma-1, lb, rb); 29 k = k - ( mb - lb + 1); 30 return f(la, ra, mb+1, rb); 31 } 32 } 33 34 int main() 35 { 36 int m,n,i; 37 38 scanf("%d%d%d",&m,&n,&k); 39 for(i=0; i<m; i++) 40 scanf("%d",&a[i]); 41 for(i=0; i<n; i++) 42 scanf("%d",&b[i]); 43 printf("%d\n",f(0,m-1,0,n-1)); 44 return 0; 45 }