AcWing 1506. 中位数(合并+sort)
原题链接
简单
作者:
Value
,
2020-06-01 09:12:51
,
所有人可见
,
阅读 894
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 4E5 + 10;
int a[N];
int main(){
int n, m;
cin >> n;
for(int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
cin >> m;
for(int i = n; i < m + n; i ++ ) scanf("%d", &a[i]);
sort(a, a + n + m);
cout << a[m + n - 1 >> 1] << endl;
return 0;
}
数据结构
#include <iostream>
using namespace std;
const int N = 2 * 1E5 + 10;
int a[N], b[N];
int Search(int n, int m){
int f = (n + m >> 1) - ((n + m + 1) % 2);
int i, j, k;
i = j = k = 0;
while(i < n && j < m){
if(a[i] < b[j]){
if(k == f) return a[i];
i ++, k ++ ;
}else{
if(k == f) return b[j];
j ++, k ++ ;
}
}
while(i < n){
if(k == f) return a[i];
i ++, k ++ ;
}
while(j < m){
if(k == f) return b[j];
j ++, k ++ ;
}
}
int main(){
int n; cin >> n;
for(int i = 0; i < n; i ++ ) cin >> a[i];
int m; cin >> m;
for(int i = 0; i < m; i ++ ) cin >> b[i];
cout << Search(n, m) << endl;
return 0;
}