最近做的ural的题目总是各种错，看了解题报告都是自己没学过的玩意，有点受打击，不过ural的题目质量还是挺好的，多被虐虐有益健康。
这一题要是用数组直接超内存，用优先级队列做，刚接触这个，学习一下优先级队列。
c++stl头文件声明<queue>, <queue>包括queue和priority_queue, priority_queue就是优先级队列。默认使用vector容器实现。优先级队列容器总是把优先级最高的元素放在队列最前方来保持队列的有序性。假如一次push 1,2,3,4,5,6，则优先级队列中存储的是6,5,4,3,2,1。
priority_queue支持的操作有：q.empty(), q.size(), q.pop(0), q.top(), q.push(item).
用法参考http://www.cplusplus.com/reference/queue/priority_queue/
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <queue> //for priority_queue 5 using namespace std; 6 int main() 7 { 8 priority_queue<unsigned int> ipq; 9 int n; 10 scanf("%d", &n); 11 unsigned int t; 12 for (int i = 1; i <= n / 2 + 1; ++i) 13 { 14 scanf("%u", &t); 15 ipq.push(t); 16 } 17 int tn = n / 2 + 2; 18 while (tn <= n) 19 { 20 scanf("%u", &t); 21 ipq.push(t); 22 ++tn; 23 ipq.pop(); 24 } 25 if (n & 1) //if n is odd 26 printf("%u.0\n", ipq.top()); 27 else 28 { 29 int t1 = ipq.top(); 30 ipq.pop(); 31 printf("%.1f", (double)(t1 + ipq.top()) / 2); 32 } 33 return 0; 34 }
还有两点需要注意的：1.结果的格式，如果中位数是整数也要输出.0，保留一位小数。2数据类型，虽然每个数都小于2^31-1，但是可能会出现中间有两个数都是INT_MAX的情况，例如n=4且四个数都是2^31-1,中间两个数相加时就会超出INT_MAX输出-1.
程序的思路就是：先把前n/2+1个元素加入优先级队列，此时优先级队列递减排列，以后每加入一个元素之后删除对头最大元素，当所有元素入队后，由于最大元素不断被删除，最后对头元素就是中位数。（分别处理n为奇数偶数的情况）