題目描述
長為L的升序序列S，S[L / 2]為其中位數。
給出兩個等長升序序列S1和S2，求兩序列合并并排序后的中位數。
輸入
多組數據，每組第一行為n，表示兩個等長升序序列的長度。
接下來n行為升序序列S1的元素，再接下來n行為升序序列S2的元素。
1 <= n <= 10 ^ 5，S內容為整數。
不超過5組數據。
輸出
每組數據，輸出合并并排序后的序列的中位數。
樣例輸入
5
11
13
15
17
19
2
4
6
8
20
樣例輸出
11
?本來以為是可以直接排序過，但是沒想到數據卡的太死。唉！還是太年輕啊！
//用二分的思想，直接遞歸求中位數#include <stdio.h>const int MAX = 100005 ;
int a[MAX], b[MAX], n;int get_middle_number(int a[], int b[], int n)
{int start1 = 0, end1 = n-1, m1;int start2 = 0, end2 = n-1, m2;while (start1 != end1 || start2 != end2){m1 = (start1 + end1) / 2;m2 = (start2 + end2) / 2;if (a[m1] == b[m2])return a[m1];if (a[m1] < b[m2]){if ((start1+end1) % 2 == 0){start1 = m1;end2 = m2;}else{start1 = m1 + 1;end2 = m2;}}else{if ((start1+end1) % 2 == 0){end1 = m1;start2 = m2;}else{end1 = m1;start2 = m2 + 1;}}}return a[start1] < b[start2] ? a[start1] : b[start2];
}int main()
{char str[10];while(scanf("%d",&n)!=EOF){int count1 = 0, flag = 0, k=0;for(int i=0; i<n; i++)scanf("%d",&a[i]);for(int i=0; i<n; i++)scanf("%d",&b[i]);int mid = get_middle_number(a,b,n);printf("%d\n",mid);}return 0;
}
?
