欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

PAT(A)1029 Median (25分)

程序员文章站 2022-07-08 22:20:42
...

PAT(A)1029 Median (25分)

Sample Input

4 11 12 13 14
5 9 10 15 16 17

Sample Output

13

思路: 这题居然卡了内存,题意就是在两个有序数组合并,并找中位数。
正常做法会内存超限,可以先输入一个数组,然后动态操作第二个数组,中位数位置是(n + m + 1) / 2。寻找对应位置的数字,如果第二个数组输入完依旧没有,重新回到第一个数组里继续。
感谢柳神。
代码:

#include <iostream>
#include <cstdio>

using namespace std;

typedef long long ll;

ll a[200005];

int main()
{
    int n;

    scanf("%d", &n);

    for (int i = 1; i <= n; ++i)
        scanf("%lld", &a[i]);

    int m;

    scanf("%d", &m);

    int cnt = 0, i = 1;
    int mid = (n + m + 1) / 2;

    a[n + 1] = 0x7fffffff;

    for (int j = 1; j <= m; ++j)
    {
        ll temp;
        scanf("%lld", &temp);

        while (a[i] < temp)
        {
            cnt++;
            if (cnt == mid)
                printf("%lld\n", a[i]);
            i++;
        }

        cnt++;
        if (cnt == mid)
            printf("%lld\n", temp);
    }

    while (i <= n)
    {
        cnt++;
        if (cnt == mid)
            printf("%lld\n", a[i]);
        i++;
    }

    return 0;
}