/*  Name: P1168_中位數(shù)  Copyright:   Author: 巧若拙   Date: 01-03-17 07:37  Description:   P1168 中位數(shù)題目描述給出一個(gè)長(zhǎng)度為N的非負(fù)整數(shù)序列A[i]，對(duì)于所有1 ≤ k ≤ (N + 1) / 2，輸出A[1], A[3], …, A[2k - 1]的中位數(shù)。即前1，3，5，……個(gè)數(shù)的中位數(shù)。輸入輸出格式輸入格式：輸入文件median.in的第1行為一個(gè)正整數(shù)N，表示了序列長(zhǎng)度。第2行包含N個(gè)非負(fù)整數(shù)A[i] (A[i] ≤ 10^9)。輸出格式：輸出文件median.out包含(N + 1) / 2行，第i行為A[1], A[3], …, A[2i – 1]的中位數(shù)。輸入輸出樣例輸入樣例#1：71 3 5 7 9 11 6輸出樣例#1：1356說(shuō)明對(duì)于20%的數(shù)據(jù)，N ≤ 100；對(duì)于40%的數(shù)據(jù)，N ≤ 3000；對(duì)于100%的數(shù)據(jù)，N ≤ 100000。算法思路：左右分別構(gòu)造一個(gè)最大堆L和最小堆R，把中位數(shù)作為最大堆的堆頂元素。先讀入第一個(gè)數(shù)，其即第一個(gè)中位數(shù)L.top()； 之后每次讀入兩個(gè)數(shù)，若小于L.top()，插入到最大堆，否則插入到最小堆；若讀入的兩個(gè)數(shù)是插入到同一個(gè)堆中，則需要?jiǎng)h除該堆的堆頂元素，插入到另一個(gè)堆中，以確保兩個(gè)堆的結(jié)點(diǎn)數(shù)滿足maxHeapSize-minHeapSize==1。 注意：要小心當(dāng)n為偶數(shù)的情形，最后一個(gè)數(shù)字是沒(méi)有用的，所以只處理前2*i-1個(gè)數(shù)字 分點(diǎn)信息（鼠標(biāo)移到方塊上有詳細(xì)信息）#1AC2ms/1378kB #2AC13ms/16421kB #3AC272ms/1687kB #4AC408ms/1710kB #5AC449ms/1664kB*/#include<iostream>#include<algorithm>#include<math.h>#include<queue>using namespace std;int main(){ 	PRiority_queue<int> L; //左側(cè)的最大堆L	priority_queue<int, vector<int>, greater<int> > R; //右側(cè)的最小堆R 	int n, x;		cin >> n;	cin >> x;	L.push(x); //把中位數(shù)存放在左側(cè)的最大堆L中 	cout << L.top() << endl;//輸出中位數(shù)	 	for (int i = 1; i <= ((n-1)>>1); i++)//只處理前2*i-1個(gè)數(shù)字 	{		int l_r = 0; //用來(lái)表示新讀入的兩個(gè)數(shù)是插入到了左側(cè)還是右側(cè)，左側(cè)--，右側(cè)++ 	 	for(int j=0; j<2; j++)	 	{		 	cin >> x;		 	if(x < L.top())		 	{				L.push(x);				l_r--;	        }			else			{				R.push(x);				l_r++;	        }		}	 			if(l_r < 0) //兩個(gè)數(shù)都插入到了L中		{			R.push(L.top());			L.pop();		}		else if(l_r > 0) //兩個(gè)數(shù)都插入到了R中		{			L.push(R.top());			R.pop();		}				cout << L.top() << endl;//輸出中位數(shù)	}	//    system("pause");				   	return 0;}