[PAT A1029]Median
题目描述
1029 Median （25 分)Given an increasing sequence S of N integers, the median is the number at the middle position. For example, the median of S1 = { 11, 12, 13, 14 } is 12, and the median of S2 = { 9, 10, 15, 16, 17 } is 15. The median of two sequences is defined to be the median of the nondecreasing sequence which contains all the elements of both sequences. For example, the median of S1 and S2 is 13.
Given two increasing sequences of integers, you are asked to find their median.
输入格式
Each input file contains one test case. Each case occupies 2 lines, each gives the information of a sequence. For each sequence, the first positive integer N (≤2×10?5??) is the size of that sequence. Then N integers follow, separated by a space. It is guaranteed that all the integers are in the range of long int.
输出格式
For each test case you should output the median of the two given sequences in a line.
输入样例
4 11 12 13 14
5 9 10 15 16 17
输出样例
13
解析
- 这道题目作为PAT甲级题通过率极低，我自己也是做了很久最终也没能做出来，只能看了柳神的代码之后自己按照思路重新写了一遍。
- 题目大意就是输入两个有序数组，要我们找他们合并数组的中位数，这题我首先想都没想直接使用一个vector存储所有数据，然后发现只拿了20分，有两个点内存超限，之后又阅读了晴神的笔记，也是有一个点内存超限（怪不得这个题目通过率这么低），所以说开两个数组是超过了内存限制了，必须在输入第二个数组的时候就边输入边处理。
- 我参考柳神的思路就是，首先由于是有序的，我们可以计算出第（n+m+1）/2个数字就是我们要找的数字，所以我们需要把两个数组合着遍历一遍，为了不超出界限，我们在第一次输入的数组的最后面加了一个整数0x7fffffff，也就是int的最大数，这样防止越界。然后我们使用t存放当前计算过的数的个数，最后只要t==（n+m+1）/2我们就可以输出该数了。我第一次总想着找到了数就break，最后导致自己各个地方出错，其实我们反正是要遍历全部数组的，由于每过滤掉一个数都会使得t++，最终正确结果都只会输出一次，所以不用break，一直循环到最后可以减少很多麻烦。
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
using namespace std;
int main()
{
int n, m;vector<int> v;scanf("%d", &n);for (int i = 0; i < n; i++) {
int temp;scanf("%d", &temp);v.push_back(temp);}v.push_back(0x7fffffff);scanf("%d", &m);int j = 0;int t = 0, cnt = (n + m + 1) / 2;for (int i = 0; i < m; i++) {
int temp;scanf("%d", &temp);while (v[j] < temp) {
t++;if (t == cnt) printf("%d", v[j]);j++;}t++;if (t == cnt) printf("%d", temp);}while (j < n) {
t++;if (t == cnt) printf("%d", v[j]);j++;}return 0;
}