URAL 1306 Sequence Median

题意:

就给你一个无序的序列,问你中位数是什么

题解:

从内存限制可以看出来,这不是排个序就能解决的。
现在维护一个堆,这个堆有至少原序列一半的元素。现在采取这样的策略:

  • 如果新进来的数字大于堆中的最大的数字,那么调整中位数的指针
  • 如果新进来的数字在堆的区间内,那么把区间中最小的那个数给pop掉,并且把新来的数给push进去

那么最后就能得到一个把中位数覆盖的数列。

代码:

https://github.com/HarryGuo2012/ACMCode/blob/worldLine/URAL/1306.cpp