PAT 1029. 中位数
原题链接
简单
作者:
YAX_AC
,
2024-11-20 20:30:59
,
所有人可见
,
阅读 3
//sequence序列 nondecreasing sequence非减序列
//The median of two sequences is defined to be the median of the nondecreasing sequence
//which contains all the elements of both sequences.
//两个序列的中值被定义为包含两个序列所有元素的非递减序列的中值。
//二路归并
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 200010;
int n,m;
int a[N],b[N],c[N*2];
int main()
{
cin>>n;
for(int i = 0; i<n; i++) cin>>a[i];
cin>>m;
for(int i = 0; i<m; i++) cin>>b[i];
int k = 0,i = 0,j = 0;
while(i<n && j<m)
if(a[i] <= b[j]) c[k++] = a[i++];
else c[k++] = b[j++];
while(i<n) c[k++] = a[i++];
while(j<m) c[k++] = b[j++];
cout<<c[(n+m-1)/2];
return 0;
}