寻找两条序列的中位数
一开始直接用库里的sort好像超时
最后改为并归排序（复杂度只有n）
#include <iostream> #include <cstdio> #include <vector> using namespace std; int n1,n2; int main() { int i; long x; cin>>n1; vector<long> seqa; for(i=0;i<n1;i++){ scanf("%ld", &x); seqa.push_back(x); } cin>>n2; vector<long> seqb; for(i=0;i<n2;i++){ scanf("%ld", &x); seqb.push_back(x); } vector<long> seq; int j=0; i=0; while(i<n1&&j<n2) if(seqa[i]>=seqb[j]){ seq.push_back(seqb[j]); j++; }else if(seqa[i]<seqb[j]){ seq.push_back(seqa[i]); i++; } if(i==n1){ for(;j<n2;j++) seq.push_back(seqb[j]); }else if(j==n2){ for(;i<n1;i++) seq.push_back(seqa[i]); } cout<<seq[(n1+n2-1)/2]<<endl; return 0; }