7-53 两个有序序列的中位数 (25 分)
已知有两个等长的非降序序列S1, S2, 设计函数求S1与S2并集的中位数。有序序列A0,A1,⋯,A**N−1的中位数指A(N−1)/2的值,即第⌊(N+1)/2⌋个数(A0为第1个数)。
输入格式:
输入分三行。第一行给出序列的公共长度N(0<N≤100000),随后每行输入一个序列的信息,即N个非降序排列的整数。数字用空格间隔。
输出格式:
在一行中输出两个输入序列的并集序列的中位数。
输入样例1:
输出样例1:
输入样例2:
1 2 3
| 6 -100 -10 1 1 1 1 -50 0 2 3 4 5
|
输出样例2:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
| #include <stdio.h> void f(int a[],int left,int right); int a[200020]; int main(){ int n,m; scanf("%d",&n); int x=0; for (int i=0;i<n;i++){ scanf("%d",&m); a[x++]=m; } for (int i=0;i<n;i++){ scanf("%d",&m); a[x++]=m; } f(a,0,x-1); printf("%d\n",a[(2*n-1)/2]); } void f(int a[],int left,int right) { int x=a[left],i=left,j=right; if (i>=j) {return;} while (i<j) { while (i<j&&a[j]>=x) j--; a[i]=a[j]; while (i<j&&a[i]<=x) i++; a[j]=a[i]; } a[i]=x; f(a,left,i-1); f(a,i+1,right); }
|