PAT——1029 Median (25 分)

题目大意:

给两个非递减序列,求它们合并后中位数。

题目解析:

一开始用两个数组存储序列,然后计算求中位数,结果发现超出内存限制。改为存储第一个序列,第二序列边读边求,通过。

具体代码:

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define MAXN 200005
int A[MAXN];
int B;
int main()
{
	int m,n,middle;
	int res;
	scanf("%d",&m);
	for(int i=0;i<m;i++){
		scanf("%d",&A[i]);
	}
	scanf("%d",&n);
	if((m+n)%2==0)
		middle=(m+n)/2;
	else
		middle=(m+n)/2+1;
	int k=0,i=0,j=0;
	scanf("%d",&B);
	while(i<m&&j<n&&k<middle){
		if(A[i]<B)
			res=A[i++];
		else{
			res=B;
			scanf("%d",&B);
			j++;
		}
		k++;
	}
	while(i<m&&k<middle){
		res=A[i++];
		k++;
	}
	while(j<m&&k<middle){
		res=B;
		scanf("%d",&B);
		j++;
		k++;
	}
	printf("%d",res);
    return 0;
}
全部评论

相关推荐

点赞 评论 收藏
分享
06-18 13:28
已编辑
门头沟学院 Web前端
爱睡觉的冰箱哥:《给予你300的工资》,阴的没边了
点赞 评论 收藏
分享
陈逸轩1205:才105 哥们在养生呢
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
昨天 11:21
被夸真的超级开心,好可爱的姐姐
码农索隆:老色批们不用脑补了,我把金智妮的图找来了查看图片
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务