首页 > 其他 > 详细

【PAT甲级】1029 Median (25 分)

时间:2019-09-10 23:58:20      阅读:55      评论:0      收藏:0      [点我收藏+]

标签:ros   ace   median   mil   -s   size   

题意:

输入一个正整数N(<=2e5),接着输入N个非递减序的长整数。

输入一个正整数N(<=2e5),接着输入N个非递减序的长整数。(重复一次)

输出两组数合并后的中位数。(200ms,合并后排序会超时,利用两组数是有序的进行模拟)

代码:

#define HAVE_STRUCT_TIMESPEC
#include<bits/stdc++.h>
using namespace std;
long a[200007];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;++i)
cin>>a[i];
int m;
cin>>m;
long x;
int l=0,r=n+m;
int mid=(l+r-1)/2+1;
int cnt=0;
++l;
for(int i=1;i<=m;++i){
cin>>x;
while(l<=n&&a[l]<x){
++cnt;
if(cnt==mid)
cout<<a[l];
++l;
}
++cnt;
if(cnt==mid)
cout<<x;
}
while(l<=n){
++cnt;
if(cnt==mid)
cout<<a[l];
++l;
}
return 0;
}

【PAT甲级】1029 Median (25 分)

标签:ros   ace   median   mil   -s   size   

原文:https://www.cnblogs.com/ldudxy/p/11503891.html

(1)
(1)
   
举报
评论 一句话评论(0
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号