网页制作如何新建站点,找人做的网站推广被坑,vps云服务器免费,wordpress小清新题目描述 长为L的升序序列S#xff0c;S[L / 2]为其中位数。 给出两个等长升序序列S1和S2#xff0c;求两序列合并并排序后的中位数。 输入 多组数据#xff0c;每组第一行为n#xff0c;表示两个等长升序序列的长度。 接下来n行为升序序列S1的元素#xff0c;再接下来n行…题目描述 长为L的升序序列SS[L / 2]为其中位数。 给出两个等长升序序列S1和S2求两序列合并并排序后的中位数。 输入 多组数据每组第一行为n表示两个等长升序序列的长度。 接下来n行为升序序列S1的元素再接下来n行为升序序列S2的元素。 1 n 10 ^ 5S内容为整数。 不超过5组数据。 输出 每组数据输出合并并排序后的序列的中位数。 样例输入 5
11
13
15
17
19
2
4
6
8
20样例输出 11 本来以为是可以直接排序过但是没想到数据卡的太死。唉还是太年轻啊 //用二分的思想直接递归求中位数#include stdio.hconst int MAX 100005 ;
int a[MAX], b[MAX], n;int get_middle_number(int a[], int b[], int n)
{int start1 0, end1 n-1, m1;int start2 0, end2 n-1, m2;while (start1 ! end1 || start2 ! end2){m1 (start1 end1) / 2;m2 (start2 end2) / 2;if (a[m1] b[m2])return a[m1];if (a[m1] b[m2]){if ((start1end1) % 2 0){start1 m1;end2 m2;}else{start1 m1 1;end2 m2;}}else{if ((start1end1) % 2 0){end1 m1;start2 m2;}else{end1 m1;start2 m2 1;}}}return a[start1] b[start2] ? a[start1] : b[start2];
}int main()
{char str[10];while(scanf(%d,n)!EOF){int count1 0, flag 0, k0;for(int i0; in; i)scanf(%d,a[i]);for(int i0; in; i)scanf(%d,b[i]);int mid get_middle_number(a,b,n);printf(%d\n,mid);}return 0;
}转载于:https://www.cnblogs.com/Asimple/p/5495242.html