PAT(A)1029 Median (25分)
程序员文章站
2022-07-08 22:20:42
...
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;
}