阅读排行

2-13. 两个有序序列的中位数（25）（ZJUPAT ）

题目链接：http://pat.zju.edu.cn/contests/ds/2-13

已知有两个等长的非降序序列S1, S2, 设计函数求S1与S2并集的中位数。有序序列A₀, A₁…A_N-1的中位数指A_(N-1)/2的值,即第[(N+1)/2]个数（A₀为第1个数）。

输入格式说明：

输入分3行。第1行给出序列的公共长度N（0<N<=100000），随后每行输入一个序列的信息，即N个非降序排列的整数。数字用空格间隔。

输出格式说明：

在一行中输出两个输入序列的并集序列的中位数。

样例输入与输出：

序号	输入	输出
1	5 1 3 5 7 9 2 3 4 5 6	4
2	6 -100 -10 1 1 1 1 -50 0 2 3 4 5	1
3	3 1 2 3 4 5 6	3
4	3 4 5 6 1 2 3	3
5	1 2 1	1

技术文章

PS:

这题说多了都是满满的都是泪，怪自己智商捉急，看见题目里的的并集，就煞笔的去了重，然后……然后最后一个案例WA到吐都过不了！用了各种方法…………

技术文章

代码如下：

#include <cstdio>
#include <cstring>
const int maxn = 100017;
int a[maxn], b[maxn], c[maxn];
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        for(int i = 0; i < n; i++)
        {
            scanf("%d",&a[i]);
        }
        for(int i = 0; i < n; i++)
        {
            scanf("%d",&b[i]);
        }
        int l = 0;
        int i = 0, j = 0;
        while(i < n && j < n)
        {
            if(a[i] == b[j])
            {
                c[l++] = a[i];
                c[l++] = b[j];//这一行开始没加WA到吐
                i++,j++;
            }
            if(a[i] < b[j])
            {
                c[l++] = a[i];
                i++;
            }
            else
            {
                c[l++] = b[j];
                j++;
            }
        }
        while(i < n)
        {
            c[l++] = a[i];
            i++;
        }
        while(j < n)
        {
            c[l++] = b[j];
            j++;
        }
        printf("%d\n",c[(l-1)/2]);
    }
    return 0;
}

文章来自：http://blog.csdn.net/u012860063/article/details/39677005