同和新媒体矩阵官网同和视频矩阵同和素材矩阵

登录 | 立即注册

同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

1567_中位数

2022-5-16 18:17| 发布者: Hocassian| 查看: 39| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-2-89503978789200-Problem List-采集的数据-后羿采集器.html

Pro.ID

1567

Title

中位数

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=1567

AC

50

Submit

209

Ratio

23.92%

时间&空间限制

Time Limit: 4000/1000 MS (Java/Others) Memory Limit: 32768/10000 K (Java/Others)

描述

一个长度为L (L ≥ 1)的升序序列S，处在第[L/2]个位置的数称为S的中位数。例如，若序列S₁=(11, 13, 15, 17, 19)，则S₁的中位数是15。两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S₂= (2, 4, 6, 8, 20)，则S₁和S₂的中位数是11。

给出两个有序序列A和B，它们的长度相等。设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A和B的中位数。

输入

单测试用例。

第一行是L，表示两个有序序列A和B的长度。1 < L ≤ 1000000

第二行是序列A，空格分隔的L个整数。

第三行是序列B，空格分隔的L个整数。

输出

Description

一个长度为L (L ≥ 1)的升序序列S，处在第[L/2]个位置的数称为S的中位数。例如，若序列S₁=(11, 13, 15, 17, 19)，则S₁的中位数是15。两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S₂= (2, 4, 6, 8, 20)，则S₁和S₂的中位数是11。

给出两个有序序列A和B，它们的长度相等。设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A和B的中位数。

Input

单测试用例。

第一行是L，表示两个有序序列A和B的长度。1 < L ≤ 1000000

第二行是序列A，空格分隔的L个整数。

第三行是序列B，空格分隔的L个整数。

Output

输出一个整数，A和B的中位数。无需换行。

Sample Input

5
11 13 15 17 19
2 4 6 8 20

Sample Output

11

Author

样例输入

5
11 13 15 17 19
2 4 6 8 20

样例输出

11

提示

作者

最新评论

相关分类

返回顶部