PAT Advanced 1029 Median （25 ）

• • 題目描述
  • Input Specification:
  • Output Specification:
  • Sample Input:
  • Sample Output:
  • 解題思路
  • Code

題目描述

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.

Input Specification:

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 10​^5 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.

Output Specification:

For each test case you should output the median of the two given sequences in a line.

Sample Input:

4 11 12 13 14
5 9 10 15 16 17
           

Sample Output:

13
           

解題思路

這題嚴重卡空間，兩個數組是不能都存下來的，

long int

即

int

是4個位元組，輸入的一個數組的長度N (≤2× 10 ​ 5 10​^5 10​5​​) ，是以整個數組存在來的空間是8x 1 0 5 10^5 105B，存兩個就超過記憶體限制的1.5MB空間了。但是第一個數組可以用隊列存下來，然後對第二個數組線上操作，進第二個隊列後，比較兩個隊列的首元素，把更小的出列，直到第（n1+n2+1)/2個元素。要注意讀完第二個數組仍然可能沒有找到，是以還要繼續尋找。其中有個技巧就是讀完一個隊列後在其最後面加上

int

的最大值

0x7fffffff

，避免對空隊列操作。

Code

• AC代碼

#include<bits/stdc++.h>
using namespace std;
const int INF = 0x7fffffff;
void pop(queue<int> &q1, queue<int> &q2, int &cnt) {
	q1.front() <= q2.front() ? q1.pop() : q2.pop();
	cnt++;
}
int main() {
	//freopen("in.txt", "r", stdin);
	ios::sync_with_stdio(false);
	int n1, n2, cnt = 0, temp;
	cin >> n1;
	queue<int> q1, q2;
	for(int i = 0; i<n1; i++) {
		cin >> temp;
		q1.push(temp);
	}
	q1.push(INF);
	cin >> n2;
	int mid = (n1+n2-1)/2;
	for(int i = 0; i<n2; i++) {
		cin >> temp;
		q2.push(temp);
		if(cnt == mid) {
			cout << min(q1.front(), q2.front());
			return 0;
		}
		pop(q1, q2, cnt);
	}
	q2.push(INF);
	while(cnt != mid) {
		pop(q1, q2, cnt);
	}
	cout << min(q1.front(), q2.front());
	return 0;
}